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

Question

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

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

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

Answer 1

您的声明"如果数据结构是一个数据结构,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

但是,如果某事既是a Foldable又是Monoid任何相关的方式,我希望以下同态定律能够成立:

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

我们不能坚持这些法律TwoThings.请注意,foldMap (:[]) a对于TwoThings总是有两个元素.但是第二定律左边有两个元素,右边有四个元素.但正如dfeuer的答案所示,法律并不需要找到反例.

Answer 2

这是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 = ????