scala - 如果数据结构是可折叠的，它是幺半群吗？

Question

显然，如果一个数据结构是一个幺半群，它就是可折叠的，但是可以肯定地说如果一个数据结构是可折叠的，它就是一个幺半群吗？

https://en.wikibooks.org/wiki/Haskell/Foldable

如果数据结构是可折叠的，它是幺半群吗？

Answer 1

您的主张“如果数据结构是 Monoid 那么它是可折叠”并不合理。例如:

newtype ActionList a = ActionList (IO [a])

instance Monoid (ActionList a) where
    mempty = ActionList (return [])
    ActionList a `mappend` ActionList b = ActionList (liftA2 (++) a b)

这是一个完美的幺半群。但由于它的所有值都位于 IO 下，因此您无法从 Foldable 中观察到它们中的任何一个。唯一的 Foldable 实例将是始终返回空的实例(从技术上讲，这是有效的，因为 foldMap 实际上没有任何关于其有效性的法律，但很难板着脸说这是一个很好的例子)。

您所问的相反情况也是不正确的。例如:

data TwoThings a = TwoThings a a

这是可折叠的:

instance Foldable TwoThings where
    foldMap f (TwoThings x y) = f x <> f y

但是，如果某物以任何相关方式既是 Foldable 又是 Monoid，我希望以下同态定律成立:

foldMap f mempty = mempty
foldMap f (a <> b) = foldMap f a <> foldMap f b

我们无法让这些定律适用于 TwoThings。请注意，TwoThings 的 foldMap (:[]) a 始终有两个元素。但第二定律左边有两个元素，右边有四个元素。但法律并不需要找到反例，如 dfeuer's answer显示。