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

Question

在李亚赫中，有一段代码如下所示。

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文档，有各种链接可以查看源代码。我就是这么做的。