60

实例可能是Foldable某种容器，因此也可能是Functor。确实，这说

一个Foldable类型也是一个容器（虽然这个类在技术上并不需要Functor，但有趣Foldable的都是Functors）。

那么有没有一个Foldable自然不是 aFunctor或 a的例子Traversable？（也许 Haskell wiki 页面错过了 :-)）

4

3 回答 3

61

这是一个完全参数化的示例：

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

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

Weird不是Functor因为a出现在否定位置。

于 2011-12-02T16:41:41.363 回答
54

这是一个简单的例子：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这使您引用的关于“有趣” Foldables 的评论似乎有点可疑！

于 2011-12-02T16:16:23.617 回答
27

阅读美丽的折叠 我意识到任何东西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共单数据类型的一种变体。）

现在我们可以定义

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 VisscherWeird都是函子。（然而，由于该结构不会记住它的值，如果我们使用的函数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。

于 2012-10-15T13:21:22.820 回答