W jaki sposób Foldable.foldl działa na Num a =>

Question

W LYAH, jest kawałek kodu, który wygląda tak.

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 

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

O ile mi wiadomo, foldMap jest typu foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m, ale sama w sobie nie jest Num a => a typu Monoid, więc zastanawiam się w jaki sposób Foldable.foldl faktycznie tu pracować? A ponieważ foldMap nazywa się wewnętrznie przez Foldable.foldl, jaki jest typ Monoid?

Answer 1

Jest nieco łatwiej dowiedzieć się, czy uważasz, foldr, który ma typ (a -> b -> b) -> b -> t a -> b. Funkcja "algebry" ma typ a -> b -> b, który można wyświetlić jako a -> (b -> b) - tj. Funkcję, która przyjmuje a jako dane wejściowe i zwraca b -> b jako wynik.

Teraz b -> b jest endomorfizm, który jest również monoid i Data.Monoid definiuje typ Endo a (lub tutaj, to powinien chyba być Endo b), który jest rzeczywiście, Monoid.

foldr prostu wykorzystuje Endo wewnętrznie zadzwonić foldMap:

foldr :: (a -> b -> b) -> b -> t a -> b 
foldr f z t = appEndo (foldMap (Endo #. f) t) z 

foldl zasadzie tylko odwraca argumenty wokół, aby zrobić to samo trick:

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

Żeby było jasne, ja dosłownie skopiowane te implementacja dwóch funkcji ze źródła Haskella. Jeśli przejdziesz do documentation of Data.Foldable, istnieją różne linki do wyświetlenia źródła. To jest to co zrobiłem.