可折叠的一个例子,它不是一个Functor(或不是Traversable)？

Question

一个Foldable实例可能是某种容器,因此也可能是一个容器Functor.确实,这说

一个Foldable类型也是一个容器(虽然类不技术上要求Functor,有趣Foldables为所有Functor为s).

那么有一个例子,Foldable它不是自然的a Functor或a Traversable？(也许Haskell维基页错过了:-))

Answer 1

这是一个完全参数化的例子:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird不是Functor因为a发生在负面的位置.

Answer 2

这是一个简单的例子:Data.Set.Set.你自己看.

如果您检查为以下内容定义的专用fold和map函数的类型,原因应该是显而易见的Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

由于数据结构在内部依赖于二叉搜索树,Ord因此元素需要约束.Functor实例必须允许任何元素类型,因此这是不可行的,唉.

另一方面,折叠总是破坏树以产生汇总值,因此不需要对折叠的中间结果进行排序.即使折叠实际上是在构建新的Set,但是满足Ord约束的责任在于传递给折叠的累积函数,而不是折叠本身.

同样可能适用于任何不完全参数化的容器类型.考虑到实用性,我认为Data.Set你引用的关于"有趣"的Foldable评论似乎有点可疑!

Answer 3

阅读美丽的折叠 我意识到任何Foldable可以Functor通过包装进入

data Store f a b = Store (f a) (a -> b)

使用简单的智能构造器:

store :: f a -> Store f a a
store x = Store x id

(这只是Store comonad数据类型的变体.)

现在我们可以定义

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

通过这种方式,我们可以让两个Data.Set.Set人和Sjoerd Visscher Weird成为一个算符.(但是,由于结构不会记住它的值,如果我们使用的函数fmap很复杂,反复折叠它可能是非常低效的.)

更新:这也提供了一个结构的示例,该结构是一个可折叠但可折叠但不可遍历的仿函数.为了实现可Store遍历,我们需要进行(->) r遍历.所以我们需要实施

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

我们来Either b接受吧f.然后我们需要实施

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

显然,没有这样的功能(你可以用Djinn验证).所以我们都无法实现sequenceA.