4

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

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
4

2 回答 2

2

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

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

幺半群[wiki]是一种代数结构。它本质上是一个 3 元组(S, ⊕, s 0 )，其中S是值的集合，⊕ :: S × S → S是关联二元运算符，并且s 0是单位元素，因此s 0 ⊕ s = s ⊕ s 0 = s。

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

通过使用foldMap，我们将在这些元素上调用一个函数f :: a -> m，并使用 monoid 函数⊕来“折叠”这些值。因此，对于同样实现的数据结构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在这些项目上调用折叠函数。

于 2019-09-30T09:37:25.177 回答
2

所以你有以下签名：foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m. 让我们一步一步来

约束：

aMonoid是可以通过某种操作组合的数据。如果你想一想，你可以得到很多例子。这里只提一下：

  • Integer作为数据和+操作。元素1和2可以结合给予3 = 1 + 2。
  • Integer作为数据和*操作。元素1和2可以结合给予2 = 1 * 2。
  • List作为数据和++操作。元素[1,2]和[2,3]可以结合给予[1,2,2,3] = [1,2] ++ [2,3]。
  • Vector大小为 2 的数据和+操作。元素<1,2>和<4,5>可以结合给予<5,7> = <1,2> + <4,5>。
  • ETC..

上面所有的例子都有一个Monoid在haskell中的表示，通常使用newtype或data关键字来定义。在 haskell 中，幺半群操作表示为<>。

一个重要的属性是幺半群具有中性元素并且是关联的。Integer在+中性元素的上下文中，0关联性是由事实给出的(a + b) + c = a + (b + c)。您可以在所有给定的示例中轻松找到此属性。试用！

Foldable约束更容易。本质上，您可以将Foldable数据结构汇总为一个值。

功能参数

代码价值千言万语，所以...

foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
--          ^^^^^^^^^^^^^^^^^^^^     ^^^^^^^     ^^^
--          |- We've seen this       |           |
--                                   |           |- A 'Set' of a's which can be collapse into a single value
--                                   |- A function to convert a's into a monoid

因此，根据定义，您可以轻松遵循以下推理/算法：

前提

  1. 我有一个可以折叠成单个值的元素结构
  2. 我有办法将这些元素转换成一个幺半群的元素
  3. Monoids 有一个中性元素
  4. 两个幺半群元素可以组合在一起

算法

  • 通过使用 monoid 算子组合结构的元素来折叠结构的元素
  • 如果结构为空，则使用中性元素作为结果。

很花哨，但是……我还是没听懂

问题是当你定义一个 的实例时Foldable，你还没有定义如何折叠结构，而且每个都不同！正如在威廉的回答中，您可以定义foldMap,foldr意思foldr是定义您可以折叠结构的方式。反之亦然：您可以根据 来定义foldr，foldMap这可能就是问题所在！如果您还没有定义foldr，则没有通用的实现方式foldMap，这取决于您的数据结构。因此，作为代码摘要：

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m -- A default instance can be provided if you define foldr (a.k.a a way to collapse the structure)
  foldr   :: (a -> b -> b) -> b -> t a -> b  -- A default instance can be provided if you define foldMap (a.k.a a way to collapse the structure into a monoid element)
  -- but if you don't provide at least one, It'll be impossible to implement any
  -- because you aren't telling me how to collapse the structure!!
于 2019-09-30T10:32:19.007 回答