类型foldMap :: (Monoid m) => (a -> m) -> fa -> m 是什么意思以及如何实现它？

Question

有人可以解释该类型的含义以及如何实现它吗？

\n\n

class Foldable f where\n  foldMap :: (Monoid m) => (a -> m) -> f a -> m\n

\n\n

基于https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-Foldable.html#v:foldMap，\n他们将其解释为“将结构的每个元素映射到幺半群，然后组合结果。” 但我不太明白这意味着什么。如何将元素映射到 Monoid 的结构？

\n\n

我尝试了 \n foldMap f = mconcat . (<$>) f\n但收到此错误：

\n\n

 \xe2\x80\xa2 Couldn\'t match type \xe2\x80\x98f\xe2\x80\x99 with \xe2\x80\x98[]\xe2\x80\x99\n      \xe2\x80\x98f\xe2\x80\x99 is a rigid type variable bound by\n        the class declaration for \xe2\x80\x98Foldable\xe2\x80\x99\n        at traversable.hs:41:16\n      Expected type: f a -> m\n        Actual type: [a] -> m\n    \xe2\x80\xa2 In the expression: mconcat . (<$>) f\n      In an equation for \xe2\x80\x98foldMap\xe2\x80\x99: foldMap f = mconcat . (<$>) f\n    \xe2\x80\xa2 Relevant bindings include\n        foldMap :: (a -> m) -> f a -> m (bound at traversable.hs:45:3)\n

\n\n

我尝试了 @WillemVanOnsem\ 的代码并收到此错误：

\n\n

error:\n    \xe2\x80\xa2 Could not deduce (Data.Foldable.Foldable f)\n        arising from a use of \xe2\x80\x98foldr\xe2\x80\x99\n      from the context: Foldable f\n        bound by the class declaration for \xe2\x80\x98Foldable\xe2\x80\x99\n        at traversable.hs:41:7-14\n      or from: Monoid m\n        bound by the type signature for:\n                   foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m\n        at traversable.hs:42:14-47\n      Possible fix:\n        add (Data.Foldable.Foldable f) to the context of\n          the type signature for:\n            foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m\n          or the class declaration for \xe2\x80\x98Foldable\xe2\x80\x99\n    \xe2\x80\xa2 In the expression: foldr (\\ x -> mappend (f x)) mempty\n      In an equation for \xe2\x80\x98foldMap\xe2\x80\x99:\n          foldMap f = foldr (\\ x -> mappend (f x)) mempty\n

\n

Answer 1

他们将其解释为“将结构的每个元素映射到幺半群，然后组合结果。” 但我不太明白这意味着什么。如何将元素映射到 Monoid 的结构？

我们使用带有签名的函数来做到这一点a -> m。所以我们自己定义“映射”函数。

幺半群[wiki]是一种代数结构。它本质上是一个三元组(S, ⊕, s ₀ )，其中S是值的集合，⊕ :: S × S → S是结合二元运算符，s ₀是单位元素，使得s ₀ ⊕ s = s ⊕ s ₀ = s。

Foldable作为类成员的类型是可以“折叠”的数据结构。这意味着，如果您有一个Tree包含Ints 的 a ，那么 a Tree Int，这样您对于一个函数f :: Int -> Int -> Int和一个中性元素z，您可以派生一个Int。

通过使用，foldMap我们将在这些元素上调用一个函数f :: a -> m，并使用幺半群函数⊕来“折叠”这些值。对于同样实现的数据结构Functor，它或多或少相当于foldMap f = foldr mappend mempty . fmap f.

然而，我们可以f在foldr函数本身中使用 the，例如：

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f x = foldr (\y -> mappend (f y)) mempty x

或更短：

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f = foldr (mappend . f) mempty

因此，在这里我们首先预处理数据结构中的值，f将它们转换为幺半群对象，然后我们对mappend这些项调用折叠函数。