不是函子（或不可遍历）的可折叠示例？

Question

可折叠 实例可能是某种容器，因此也可能是一个函子。事实上，这说

Foldable类型也是一个容器（尽管该类在技术上不需要Functor，有趣的Foldable都是Functors)。

那么是否有一个 Foldable 的例子，它本质上不是一个 Functor 或 Traversable ？ （也许 Haskell wiki 页面错过了:-)）

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。 亲自看看。

如果您检查为 Set 定义的专用 fold 和 map 函数的类型，其原因应该很明显：

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

阅读美丽的折叠
将其包装成 Functor

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

我意识到任何 Foldable 都可以通过使用简单的智能构造函数

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

：（这只是 存储 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)

Let's take Either b for f。那么我们需要实现

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

显然，没有这样的功能（你可以用 Djinn 来验证） 。所以我们都无法实现sequenceA。