当折叠图与幺半群没有任何关系时，如何与折叠器做同样的事情

Question

foldr和foldMap可以用来定义彼此，据我所知。但是这怎么可能，因为后者使用幺半群，而前者不使用呢？我们能保证foldr工作的东西可以有一个幺半群吗？

Answer 1

foldr :: (a -> b -> b) -> b -> [a] -> b

请注意，a -> b -> b是a -> (b -> b) 。函数b -> b组成下形成幺半群。

注意这类似于

foldMap :: (..omitted..) => (a -> m) -> f a -> m

唯一的区别是 foldMap 不使用 fold 类型b的 "零" 参数并返回一个 m，就foldr而言，这将是b->b。现在只需将一个应用于另一个，您就可以从foldMap中恢复foldr。