Monoides y Num en Haskell

monoids

Question

He estado aprendiendo Haskell durante los últimos meses y me encontré con un ejemplo de Monoids que me ha desconcertado.

Dadas estas definiciones:

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  

Y este árbol:

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

Si corro:

ghci> F.foldl (+) 0 testTree  
42  
ghci> F.foldl (*) 1 testTree  
64800  

¿Cómo sabe GHCi qué Monoide usar para el mappend cuando se pliega? Porque, de forma predeterminada, los números en el árbol son solo del tipo Num, y nunca dijimos explícitamente dónde estaban algunos de los Monoides como Suma o Producto.

Entonces, ¿cómo GHCi infiere el Monoide correcto para usar? ¿O estoy totalmente fuera en este punto?

Fuente de ejemplo: http://learnyouahaskell.com/functors-applicative-functors-and-monoids#monoids

Answer 1

Existe (implícitamente, si no explícitamente), una instancia de monoide para funciones ordinarias de la forma a -> a , donde mappend corresponde a la composición de la función, y mempty corresponde a la función id .

¿Qué es (+) ? Es una función (Num a) => a -> a -> a . Si foldMap el foldMap sobre tu número de números plegable con + , conviertes cada uno en el parcialmente aplicado (+ <some number) , que es un a -> a . ¡Y he aquí que has encontrado la magia que convertirá todo en tu plegable en un monoide!

Suponiendo que hubiera una instancia de monoide directa para funciones, podría hacer:

foldMap (+) [1, 2, 3, 4]

, que produciría un final (Num a) => a -> a que podría aplicar a 0 para obtener 10 .

Sin embargo, no existe tal instancia directa, por lo que necesita usar el envoltorio de newtype incorporado Endo y la aplicación correspondiente de appEndo , que implementa appEndo para a -> a funciones. Esto es lo que parece:

Prelude Data.Monoid> (appEndo (foldMap (Endo . (+)) [1, 2, 3, 4])) 0
10

Aquí Endo . es solo nuestra molesta necesidad de levantar la llanura a -> a s para que tengan su instancia natural de Monoid . Después de que foldMap reducir nuestro plegado convirtiendo todo en a -> a sy encadenándolos con la composición, extraemos el a -> a final usando appEndo y finalmente lo aplicamos a 0 .

Answer 2

No es necesario. foldl se traduce en foldr que se traduce en foldMap sobre Endo que significa composición de la función, lo que significa un simple anidamiento de la función que ha suministrado .

O algo. Es decir, foldl podría traducirse a foldMap sobre Dual . Endo Dual . Endo que compone de izquierda a derecha, etc.

actualización: sí, la documentación dice :

Se espera que las instancias plegables cumplan las siguientes leyes:

foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z  -- << --
fold = foldMap id

Dual (Endo f) <> Dual (Endo g) = Dual (Endo g <> Endo f) = Dual (Endo (g . f)) . Entonces, cuando appEndo ataca, la cadena de funciones que se ha construido, es decir,

    ((+10) . (+9) . (+8) . (+5) . ... . (+1))

o equivalente (aquí, que se muestra para el caso (+) ), se aplica al valor proporcionado por el usuario, en su caso,

                                                 0

Otra cosa a tener en cuenta es que Endo y Dual son newtype , por lo que todas estas maquinaciones las realizará el compilador y desaparecerán en el tiempo de ejecución.

Answer 3

Respuesta corta : es una restricción de tipo en la firma de foldMap .

Si nos fijamos en el código fuente de Foldable (más específicamente foldMap ), vemos:

class Foldable (t :: * -> *) where
  ...
  foldMap :: Monoid m => (a -> m) -> t a -> m

Entonces, eso significa que si declaramos que Tree es miembro de Foldable (no que Tree tenga el tipo * -> * ), significa que un foldMap se define sobre ese árbol, de manera que: foldMap :: Monoid m => (a -> m) -> Tree a -> m . Entonces, esto significa que el tipo de resultado (y el resultado de la función pasada a foldMap ) m debe ser un Monoid .

Haskell se escribe de forma estática: después del tiempo de compilación, Haskell sabe exactamente los tipos que se pasan en una instancia de cada función. Eso significa que sabe, por ejemplo, cuál será el tipo de salida y, por lo tanto, cómo manejarlo.

Ahora Int no es una instancia de Monoid . Aquí usa F.foldl (+) 0 testTree , lo que significa que más o menos ha construido un monoide "ad hoc". Esto funciona si nos fijamos en el código fuente de foldl :

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

Esto tiene mucha lógica alrededor de los parámetros f , z y t . Así que vamos a romper eso primero.

Primero echemos un vistazo a Dual . Endo . flip f Dual . Endo . flip f Dual . Endo . flip f . Esto es corto para:

helper = /x -> Dual (Endo (/y -> f y x))

Dual y Endo son tipos con cada constructor que toma un parámetro. Así que fyx el resultado de fyx en los constructores Dual (Endo ...) .

Usaremos esto como la función de foldMap . Si nuestra f tiene el tipo a -> b -> a , entonces esta función tiene el tipo b -> Dual (Endo a) . Por lo tanto, el tipo de salida de la función pasada a foldMap tiene un tipo de salida Dual (Endo a) . Ahora, si inspeccionamos el código fuente, vemos dos cosas interesantes:

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

instance Monoid a => Monoid (Dual a) where
        mempty = Dual mempty
        Dual x `mappend` Dual y = Dual (y `mappend` x)

(tenga en cuenta que es y `mappend` x , no x `mappend` y ).

Entonces, lo que sucede aquí es que el mempty que se usa en foldMap es mempty = Dual mempty = Dual (Endo id) . Así que un Dual (Endo ...) que encapsula la función de identidad .

Además, el mappend de dos duales se reduce a la composición de la función de los valores en Endo . Asi que:

mempty = Dual (Endo id)
mappend (Dual (Endo f)) (Dual (Endo g)) = Dual (Endo (g . f))

Así que eso significa que si nos plegamos sobre el árbol, en caso de que veamos un Empty (una hoja), devolveremos mempty , y en caso de que veamos un Node xlr , realizaremos el mappend como se describe anteriormente. Así que un foldMap " especializado " se verá así:

-- specialized foldMap
foldMap f Empty = Dual (Endo id)  
foldMap f (Node x l r) =  Dual (Endo (c . b . a))
        where Dual (Endo a) = foldMap f l
              Dual (Endo b) = helper x
              Dual (Endo c) = foldMap f l

Entonces, para cada Node hacemos una composición de función de derecha a izquierda sobre los elementos secundarios y el elemento del nodo. a y c pueden ser composiciones del árbol (ya que estas son llamadas recursivas). En el caso de una Leaf , no hacemos nada (devolvemos id , pero la composición sobre una id es un no-op).

Entonces eso significa que si tenemos un árbol:

5
|- 3
|  |- 1
|  `- 6
`- 9
   |- 8
   `- 10

Esto resultará en una función:

(Dual (Endo ( (/x -> f x 10) .
              (/x -> f x 9) .
              (/x -> f x 8) .
              (/x -> f x 5) .
              (/x -> f x 6) .
              (/x -> f x 3) .
              (/x -> f x 1)
            )
      )
)

(Se omiten las identidades, para hacerla más limpia). Este es el resultado de getDual (foldMap (Dual . Endo . flip f)) . Pero ahora tenemos que postprocesar este resultado. Con getDual , obtenemos el contenido envuelto en el constructor Dual . Así que ahora tenemos:

Endo ( (/x -> f x 10) .
       (/x -> f x 9) .
       (/x -> f x 8) .
       (/x -> f x 5) .
       (/x -> f x 6) .
       (/x -> f x 3) .
       (/x -> f x 1)
     )

y con appEndo , obtenemos la función envuelta en Endo , por lo que:

( (/x -> f x 10) .
  (/x -> f x 9) .
  (/x -> f x 8) .
  (/x -> f x 5) .
  (/x -> f x 6) .
  (/x -> f x 3) .
  (/x -> f x 1)
)

y luego aplicamos esto a z el valor "inicial". Eso significa que procesaremos la cadena comenzando con z (el elemento inicial) y la aplicaremos como:

f (f (f (f (f (f (f z 1) 3) 6) 5) 8) 9) 10

Así que hemos construido algún tipo de Monoide, donde mappend es reemplazado por f , y mempty como no-op (la función de identidad).