如果数据结构是可折叠的，那么它是么半群吗？
如果数据结构是可折叠的，那么它是么半群吗？
提问于 2018-08-13 17:08:24
显然，如果一个数据结构是一个么半群，那么它是可折叠的，但是如果一个数据结构是可折叠的，那么它就是一个么？
https://en.wikibooks.org/wiki/Haskell/Foldable
如果数据结构是可折叠的，那么它是么半群吗？
回答 2
Stack Overflow用户
发布于 2018-08-13 17:57:29
你的声明“如果一个数据结构是一个Monoid，那么它就是Foldable”是不合理的。例如：
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所展示的那样，法律并不需要找到反例。
Stack Overflow用户
发布于 2018-08-14 02:48:09
下面是一些Foldable (甚至是Traversable)不可能成为Monoid的东西
{-# language EmptyCase #-}
data F a
instance Foldable F where
foldMap _ t = case t of
-- or, = mempty
instance Traversable F where
traverse _ t = case t of
-- or, = pure $ case t of
instance Semigroup (F a) where
-- the only option
x <> _ = x
instance Monoid (F a) where
mempty = ????页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51818846
复制相关文章
相似问题
腾讯云开发者
