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

Question

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

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

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

我试过 foldMap f = mconcat . (<$>) f但我收到了这个错误:

 • Couldn't match type ‘f’ with ‘[]’
      ‘f’ is a rigid type variable bound by
        the class declaration for ‘Foldable’
        at traversable.hs:41:16
      Expected type: f a -> m
        Actual type: [a] -> m
    • In the expression: mconcat . (<$>) f
      In an equation for ‘foldMap’: foldMap f = mconcat . (<$>) f
    • Relevant bindings include
        foldMap :: (a -> m) -> f a -> m (bound at traversable.hs:45:3)

我尝试了@WillemVanOnsem 的代码并得到了这个错误:

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

Answer 1

they explained it as "Map each element of the structure to a monoid, and combine the results." but I don't quite understand what it means. How can I map an element to the structure of a Monoid?

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

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

属于 Foldable class 成员的类型是可以“折叠”的数据结构。这意味着，例如，如果您有一个 Tree包含 Int s，所以 Tree Int ，这样你，对于一个函数 f :: Int -> Int -> Int ，和一个中性元素 z ，你可以得到一个 Int .

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

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

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作为这些项目的折叠功能。