Foldable.foldl如何在Num a => a上工作

Question

在LYAH中,有一段代码看起来像这样.

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  

据我所知,foldMap是类型foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m,但Num a => a本身不是类型Monoid,所以我想知道Foldable.foldl这里实际上是如何工作的？既然foldMap是内部调用Foldable.foldl,那么它的类型是Monoid什么？

Answer 1

如果考虑一下foldr,哪个类型更容易弄清楚(a -> b -> b) -> b -> t a -> b."代数"函数具有a -> b -> b您可以查看的类型a -> (b -> b)- 即:a作为输入的函数,并b -> b作为输出返回.

现在,b -> b是一个内同态,它也是一个幺半群,并Data.Monoid定义了一个类型Endo a(或者在这里,它应该是Endo b),这确实是一个类型Monoid.

foldr只需在Endo内部使用即可foldMap:

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

foldl 基本上只是翻转参数,以便做同样的伎俩:

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

为了清楚起见,我从Haskell源代码中复制了这两个函数实现.如果您转到Data.Foldable的文档,可以使用各种链接查看源.这就是我做的.