¿Es esta inferencia tipo Haskell en acción, o algo más?

Question

Estoy trabajando en el libro en línea LYAH (el enlace lo llevará directamente a la sección que me interesa).

el autor define un binario tipo de datos del árbol, y muestra cómo se puede hacer una instancia del tipo plegable (definido en Data.Foldable) mediante la implementación de la función foldMap:

import Data.Monoid 
import qualified Data.Foldable as F 

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

instance F.Foldable Tree where 
    foldMap f Empty = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

la declaración de tipo de foldMap es como sigue:

F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> t a -> m 

así que lleva una función que toma una instancia de tipo "a" y devuelve un monoide.

Ahora, como un ejemplo, el autor crea una instancia de árbol

testTree = Node 5 
       (Node 3 
        (Node 1 Empty Empty) 
        (Node 6 Empty Empty) 
       ) 
       (Node 9 
        (Node 8 Empty Empty) 
        (Node 10 Empty Empty) 
       ) 

y realiza las siguientes veces (definida para este tipo plegable):

F.foldl (+) 0 testTree -- the answer is 42 (sum of the Node Integers) 

Mi pregunta es, ¿cómo averiguar Haskell esa adición sobre el tipo Integer - consultar Haskell para el tipo de testTree da Tree [Integer] - se puede ver como una operación monoid (si mi terminología es correcta)?

(Mi propio intento de la respuesta: El autor de algunos párrafos anteriores a esta sección se describe cómo el Num tipo puede ser interpretado como un Monoid tipo de dos maneras diferentes; envolviéndolos en el Suma y Producto tipo con (+) y (*) como los mappend funciones y 0 y 1 como el elemento mempty, respectivamente. Es el tipo de "a" en (árbol a) de alguna manera se infiere como pertenecientes al Suma tipo (la forma Hask ell interpreta diversos valores numéricos de acuerdo con el contexto) o es algo totalmente diferente? ]

Answer 1

Mi pregunta es, ¿cómo averiguar Haskell que además el tipo Integer - consulta de Haskell para el tipo de testTree da Árbol [entero] - puede ser visto como una operación monoide (si mi terminología es correcta)?

¡No puede! De hecho, no existe la instancia Monoid para Integer.

Ahora, no me malinterpreten - los enteros son un monoide además. Sin embargo, también son un monoide bajo multiplicación, y Haskell no tiene forma de saber cuál usar, de ahí las envolturas newtype.

Pero ... nada de eso es lo que está sucediendo aquí. Pasando a ...

(Mi intento de respuesta: el autor algunos párrafos antes de esta sección describe cómo el tipo Num puede interpretarse como un tipo Monoid de dos maneras diferentes, envolviéndolos en la suma y Tipo de producto con (+) y (*) como las funciones mappend y 0 y 1 como el elemento mempty, respectivamente. Es el tipo de "a" en (Árbol a) de alguna manera inferido como perteneciente al tipo Suma (el camino Haskell interpreta diversamente valores numéricos de acuerdo con el contexto) o es algo completamente distinto?]

No

una mala suposición, pero ese tipo de inferencia (la búsqueda de la instancia utilizando Sum en base a los argumentos que se dio) está más allá de lo que Haskell puede hacer por usted.

Aquí hay dos puntos clave: en primer lugar, la restricción Monoid solo se usa para ciertas funciones, no para los pliegues en general. En particular, foldl en realidad no necesita una instancia de Monoid, ya que proporciona la operación binaria y el valor inicial para usar.

El segundo punto es lo que sospecho que realmente después - ¿cómo crear un genérico foldl que no necesita un Monoid, cuando todo lo que es definido foldMap, lo que hace? Para responder a esto, podemos simplemente look at the default implementation de foldl:

foldl :: (a -> b -> a) -> a -> t b -> a 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

Aquí, Endo is another newtype wrapper, específicamente para funciones a -> a dando la Monoid de la composición, con id como la identidad, mientras que Dual is a wrapper que invierte la dirección de un Monoid. Entonces, el Monoid que está usando aquí es para que pueda pegar los usos de (+) junto con la composición de la función, y luego aplicar el resultado al valor inicial.

Answer 2

El monoid no se usa realmente aquí. La última línea está usando F.foldl que tiene firma F.Foldable t => (a -> b -> a) -> a -> t b -> a. Básicamente está 'manualmente' usando un monoide suministrando (+) y 0.

Si desea utilizar un monoide 'implícitamente', puede usar F.fold (que tiene la firma (F.Foldable t, Monoid m) -> t m -> m). En este caso, si lo intenta, obtendrá:

*Main> F.fold testTree 

<interactive>:1:1: 
    No instance for (Monoid Integer) 
     arising from a use of `F.fold' 
    Possible fix: add an instance declaration for (Monoid Integer) 
    In the expression: F.fold testTree 
    In an equation for `it': it = F.fold testTree 
*Main> :t F.foldl 

Ahora, GHCi se queja de que no hay ninguna instancia Monoid por entero, como debe ser. Debe seleccionar Suma o Producto al envolver el Número entero. Para ello podemos utilizar F.foldMap (firma (F.Foldable t, Monoid m) => (a -> m) -> t a -> m):

*Main> F.foldMap Sum testTree 
Sum {getSum = 42}