作者：Hide-my-love | 来源：互联网 | 2022-12-07 19:55
显然,如果一个数据结构是一个幺半群,它是可折叠的,但如果数据结构是可折叠的,可以说它是一个幺半群吗？
https://en.wikibooks.org/wiki/Haskell/Foldable
如果数据结构是可折叠的,它是一个幺半群吗？
1> luqui..：
您的声明"如果数据结构是一个数据结构,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的答案所示,法律并不需要找到反例.
@ bayesian-study你甚至不需要`IO`就不是"可折叠".功能就足够了.存在`instance(Monoid b)=> Monoid(a - > b)`,但是你不能有效地实现`instance Foldable(( - >)a)`.
2> dfeuer..：
这是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 = ????
京公网安备 11010802041100号