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

在LYAH中，有一段代码看起来像这样。Foldable.foldl如何在数字a上工作=> a

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的类型是什么？

来源

2017-09-14 Lifu Huang

嗨@WillemVanOnsem，谢谢你的帮助。这正是我所困惑的，你提到'mempty = 1'，那么这里的'mempty'的类型是什么？我不太明白这一点，因为不像'Sum'和'Product'，'Int'不是类型'Monoid' AFAIK。你能解释一下这个吗？谢谢 –

嗯，我明白了，我是Haskell的新手，我想那是我缺少的部分。非常感谢:) –

请注意，这种技巧是非常先进的，肯定不是初学者的材料。编写一个'foldl'实现可能更容易，它首先使用'foldMap（\ x - > [x]）'将任何可折叠的元素转换为普通列表，然后执行''a''' foldl'在名单上。效率较低，但可能更易于理解。它可以使一个很好的锻炼:) – chi

如果您考虑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源码的两个函数实现。如果您转到documentation of Data.Foldable，可以通过各种链接查看源代码。这就是我所做的。

来源

2017-09-14 16:16:01

我看到，我实际上发现的源代码的一部分，但无法理解'Endo'作为我对Haskell的新角色，将读更多关于这一点。非常感谢：） –

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

回答

相关问题