一个不是 Functor（或不可遍历 Traversable）的 Foldable 的例子？

Question

一个实现Foldable的类型通常是一种容器，因此也可能是一个Functor。确实，这里说：

Foldable类型也是一种容器（尽管该类不要求技术上需要Functor，但有趣的Foldable都是Functor）。

那么是否有一个既不自然地是Functor也不是Traversable的Foldable示例呢？（也许Haskell维基页面漏掉了 :-) ）

- Prateek

Answer 1

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

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

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

Weird不是一个Functor，因为a出现在一个负面位置。

- Sjoerd Visscher

---

哦，不错！我甚至没有想到过。不知道标准库中是否有任何Foldable实例由于逆变而无法成为Functor？ - C. A. McCann

我认为你可以使用某些扩展和类型同义词来完成它。 - PyRulez

instance Functor Weird where fmap fn (Weird a aa) = Weird (fn (aa a)) id 怎么样？ - Nikita Volkov

@NikitaVolkov 不错！但它不满足函子定律。fmap id == id - Sjoerd Visscher

@SjoerdVisscher 这取决于具体情况。从技术上讲，Free 不满足单子定律，因为它的定义平等性不一致，在相同的方式下， pipes 只能通过 observe 棱镜来满足适当的法律。因此，定义平等可能不是最明智/有用/自然的方法（例如对于取商，其中定义平等成为您使用的语言的烦人副产品）。现在，你的 Weird 看起来很像 Coyoneda。而你的 foldMap 具有非常相似且特定的语义：它将 Weird 视为一个单元素容器，并总是应用存储的函数。 - effectfully

只要你总是将 Weird 中的元素提取为 runWeird (Weird x f) = f x，那么函子定律就会通过 runWeird 的棱镜得以满足。 - effectfully

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的评论似乎有点可疑！

- C. A. McCann

---

这确实是一个“可折叠”的示例，但无法成为“函子”。然而，这似乎更多是因为Haskell的类型系统无法表达“Set仅适用于Ord类型，而要使某些东西成为Functor，只需为其他定义中有意义的类型定义fmap”，而不是与“Set”和“Functor”所代表的本质相关的。无论如何，感谢提供这个例子。 :-) - Prateek

@Prateek：是和不是。完全参数化非常固有于 Functor 所代表的内容。话虽如此，比标准 Haskell 更具表达能力的类型系统（包括实际上由 GHC 支持的完整类型系统）可以表达“在某些类型类上完全参数化”，这正是所期望的。 - C. A. McCann

更数学化地讲，“Functor”只包括从所有Haskell类型构成的范畴到其自身的一个适当子范畴的特定种类的函子。它不能表达仅在子范畴上操作的函子，或者其他本应有意义的东西。话虽如此，Sjoerd Visscher的例子仍比我的更有趣也更神秘。:] - C. A. McCann

如果我们愿意接受 Set 只对 Ord 类型起作用的限制（尽管在数学中集合没有这样的限制），那么我们也应该能够容忍 Functor 中的同样不完美。 - Prateek

我相信Set并不总是需要Ord，只有在“检查”它时才需要，例如检查长度、将其显示为字符串或获取最小/最大元素等。因此，如果您允许Set在某些情况下（例如(+) <$> set）没有Ord，并且仅在具有该Ord约束时压缩和重新排序自身（因此这不能在标准Haskell中完成，但我更多地考虑从理论/数学的角度）。然后，您可以使Set成为真正的Functor，甚至是一个Applicative和一个Monad。 - semicolon

我喜欢这个答案，因为它提供了一个合理的论据来反驳看似合理的要求，即Functor是Foldable的超类。 - chepner

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共同子模式数据类型的一个变体。）

现在我们可以定义

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都成为一个functor。（然而，由于该结构不会记忆其值，如果fmap中使用的函数很复杂，反复地折叠可能非常低效。）

---

更新： 这还提供了一个既是foldable但又不能traversable的数据结构的例子。为了使Store可遍历，我们需要使(->) r可遍历。因此，我们需要实现

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

我们将 f 定义为 Either b。然后我们需要实现：

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

显然，这个函数是不存在的（你可以用Djinn进行验证）。因此我们无法实现sequenceA。

- Petr

---

Store数据类型实际上是任何类型构造器的自由函子，也被称为Coyoneda（https://hackage.haskell.org/package/kan-extensions-4.2.3/docs/Data-Functor-Coyoneda.html）。 - Kris Nuttycombe

@KrisNuttycombe 不完全是这样。Coyoneda 是存在量词，而 Store 则不是。 - Carl