haskell - 为什么非多态类型不能在 Haskell 中实现可折叠？

Question

假设我有一些简化的 lisp 风格 Expr键入如下

data Expr = String String | Cons Expr Expr
  deriving (Show)

我可以创建列表作为 Cons-cells 的 Cons-cells:

Cons (String "hello") (Cons (String "World") (String "!"))

从这里我想实现 Foldable为 Expr折叠这些缺点列表 - 但这是不可能的，因为 Foldable需要一种类型 * -> * (即仅具有一个类型参数的多态)，我的 Expr 在哪里有种 * .

这是为什么？对我来说，在这种情况下折叠非多态类型似乎是完全合理的，但显然我错过了一些东西。

Answer 1

To me it seems like folding over non-polymorphic types like in this case would be perfectly reasonable, but obviously I'm missing something.

这确实是完全合理的。折叠单态容器的一种方法是使用 MonoFoldable .另一个正在使用 a Fold from lens ，或来自其他一些光学库:

import Control.Lens

data Expr = String String | Cons Expr Expr
  deriving (Show)

-- A Traversal can also be used as a Fold.
-- strings :: Applicative f => (String -> f String) -> (Expr -> f Expr) 
strings :: Traversal' Expr String
strings f (String s) = String <$> f s
strings f (Cons l r) = Cons <$> strings f l <*> strings f r 

GHCi> hello = Cons (String "hello") (Cons (String "World") (String "!"))
GHCi> toListOf strings hello
["hello","World","!"]
GHCi> import Data.Monoid
GHCi> foldMapOf strings (Sum . length) hello
Sum {getSum = 11}

至于为什么 Foldable实例有种类 * -> *而不是 * ，我会把它归结为简单性和历史原因的结合。从历史上看， Foldable是 Traversable 的一个分支，值得注意的是，虽然单态遍历可能很有用，但它们的局限性比影响单态折叠的那些更显着(例如，您无法从中恢复 fmap，而只能恢复单态 omap) .最后，Joseph Sible 建议的问答， Is there anything we lose with MonoFoldable? ，包括一些关于不完全替换的潜在原因的有趣讨论 Foldable与 MonoFoldable .