为什么非多态类型不能在Haskell中实现Foldable？

Question

说我有一些简化的Lisp样式Expr类型，如下所示

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

我可以将列表创建为Cons-cell的Cons-cell：

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

由此我想实现Foldable的Expr折叠超过这些缺点名单-但那是不可能的，因为Foldable需要一种类型的* -> *（即多态恰好与一个类型参数），我哪来Expr有样*。

这是为什么？在我看来，像这样折叠非多态类型是完全合理的，但是显然我缺少了一些东西。

Answer 1

在我看来，像这样折叠非多态类型是完全合理的，但是显然我缺少了一些东西。

确实是完全合理的。折叠单态容器的一种方法是使用MonoFoldable。另一个是使用一个Fold由透镜，或从一些其他光学库：

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）提出的问答，“ MonoFoldable是否会使我们失去什么？，包括不彻底更换可能的原因一些有趣的讨论Foldable与 MonoFoldable。