类型 foldMap :: (Monoid m) => (a -> m) -> f a -> m 是什么意思以及如何实现它？
What does the type foldMap :: (Monoid m) => (a -> m) -> f a -> m mean and how to implement it?
谁能解释一下类型的含义以及如何实现它？
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，
他们解释为 "Map each element of the structure to a monoid, and combine the results." 但我不太明白它的意思。如何将元素映射到 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
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 的函数来做到这一点。所以我们自己定义"mapping"函数。
一个monoid [wiki]是一个代数结构。它本质上是一个三元组 (S, ⊕, s0) 其中 S 是一组值，⊕ :: S × S → S 是一个 associative 二元运算符，而 s0 是一个恒等元，这样 s0 ⊕ s = s
⊕ s0 = s.
属于 Foldable class 的类型是可以 "folded" 的数据结构。这意味着如果你有一个包含 Ints 的 Tree，那么一个 Tree Int，这样你，对于一个函数 f :: Int -> Int -> Int，和一个中性元素 z，可以推导出一个Int.
通过使用 foldMap 我们将在这些元素上调用函数 f :: a -> m，并使用幺半群函数 ⊕ 来 "fold" 值.对于也实现 Functor 的数据结构，它或多或少等同于 foldMap f = foldr mappend mempty . fmap f.
然而，我们可以在 foldr 函数本身中使用 f，例如：
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 作为这些项的折叠函数。
因此您具有以下签名：foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m。一步步来
约束条件：
a Monoid是可以通过某种操作组合的数据。如果你想一想，你可以得到很多例子。顺便提一下：
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>.- 等..
上面的所有示例在 haskell 中都有一个 Monoid 表示，通常使用 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
所以根据定义你可以很容易地遵循这个 reasoning/algorithim:
场所
- 我有一个可以折叠成单个值的元素结构
- 我有办法将这个元素转换成幺半群的元素
- 幺半群有一个中性元素
- 两个幺半群元素可以组合在一起
算法
- 通过使用幺半群运算符组合结构的元素来折叠它们
- 如果结构为空，则使用中性元素作为结果。
非常漂亮，但是...我还是不明白
问题是，当你定义一个Foldable的实例时，你还没有定义如何折叠这个结构，而且每个都不同！。正如 Willem 的回答一样，您可以根据 foldr 定义 foldMap，这意味着 foldr 正在定义折叠结构的方式。反之亦然：您可以根据 foldMap 定义 foldr，这可能就是问题所在！！如果你还没有定义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!!
谁能解释一下类型的含义以及如何实现它？
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， 他们解释为 "Map each element of the structure to a monoid, and combine the results." 但我不太明白它的意思。如何将元素映射到 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
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 的函数来做到这一点。所以我们自己定义"mapping"函数。
一个monoid [wiki]是一个代数结构。它本质上是一个三元组 (S, ⊕, s0) 其中 S 是一组值，⊕ :: S × S → S 是一个 associative 二元运算符，而 s0 是一个恒等元，这样 s0 ⊕ s = s ⊕ s0 = s.
属于 Foldable class 的类型是可以 "folded" 的数据结构。这意味着如果你有一个包含 Ints 的 Tree，那么一个 Tree Int，这样你，对于一个函数 f :: Int -> Int -> Int，和一个中性元素 z，可以推导出一个Int.
通过使用 foldMap 我们将在这些元素上调用函数 f :: a -> m，并使用幺半群函数 ⊕ 来 "fold" 值.对于也实现 Functor 的数据结构，它或多或少等同于 foldMap f = foldr mappend mempty . fmap f.
然而，我们可以在 foldr 函数本身中使用 f，例如：
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 作为这些项的折叠函数。
因此您具有以下签名：foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m。一步步来
约束条件：
a Monoid是可以通过某种操作组合的数据。如果你想一想，你可以得到很多例子。顺便提一下：
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>.- 等..
上面的所有示例在 haskell 中都有一个 Monoid 表示，通常使用 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
所以根据定义你可以很容易地遵循这个 reasoning/algorithim:
场所
- 我有一个可以折叠成单个值的元素结构
- 我有办法将这个元素转换成幺半群的元素
- 幺半群有一个中性元素
- 两个幺半群元素可以组合在一起
算法
- 通过使用幺半群运算符组合结构的元素来折叠它们
- 如果结构为空，则使用中性元素作为结果。
非常漂亮，但是...我还是不明白
问题是，当你定义一个Foldable的实例时，你还没有定义如何折叠这个结构，而且每个都不同！。正如 Willem 的回答一样，您可以根据 foldr 定义 foldMap，这意味着 foldr 正在定义折叠结构的方式。反之亦然：您可以根据 foldMap 定义 foldr，这可能就是问题所在！！如果你还没有定义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!!