haskell - 如何将 Haskell 中的 fold 函数与其他数据类型一起使用

Question

关于如何为新数据类型创建折叠函数有一种通用的思考方式吗？

例如，数据树的折叠函数是:

data Tree t = Leaf | Node t (Tree t) (Tree t)
              deriving (Eq,Ord,Show)

treeFold:: (a -> b -> b -> b) -> b -> Tree a -> b
treeFold f e Leaf = e
treeFold f e (Node x l r) = f x (treeFold f e l) (treeFold f e r)

例如，我必须如何为以下数据创建折叠函数？

data Json a = Val a | Obj [(String, Json a)]

我知道该类型必须包含 2 个函数，一个分别用于 Val 和 Obj 的情况。创建折叠时我必须考虑什么？我希望我的问题是有道理的。我刚刚遇到了许多不同的数据类型，其中要求为数据类型编写折叠函数，但我似乎没有找到模式。

Answer 1

正如 Willem Van Onsem 在(现已删除)评论中指出的那样，您尝试实现的也称为 catamorphism。我在 Does each type have a unique catamorphism? 上写了一些关于我认为你可能称之为初学者的 catamorphisms 观点的文章。 .您可以非常机械地推导出一个类型的 catamorphism(或表明没有一个类型可以存在)。如果您的类型有 N 个构造函数，则 fold 函数必须采用 N+1 个参数:您的类型的一个值，以及每个构造函数的一个函数。每个这样的函数在其对应的构造函数具有的每个字段接受一个参数(或者，如果构造函数没有字段，它接受一个普通值，您可以将其想象为一个 0 元函数)，并返回一个任何类型的值返回。

它的文字很复杂，所以我将从我上面链接的答案中复制相关代码，作为示例:

data X a b f = A Int b
             | B
             | C (f a) (X a b f)
             | D a

xCata :: (Int -> b -> r)
      -> r
      -> (f a -> r -> r)
      -> (a -> r)
      -> X a b f
      -> r
xCata a b c d v = case v of
  A i x -> a i x
  B -> b
  C f x -> c f (xCata a b c d x)
  D x -> d x

观察到每个函数(a、b、c、d)在关联的构造函数中的每个字段都有一个参数。在大多数情况下，您只需使用构造函数的每个字段调用该函数……但是 C 的情况如何？我们为什么不写 c f x而不是 c f (xCata a b c d x) ?这是递归发生的地方: cata的工作是递归遍历(折叠)由您的 ADT 表示的整个树，转动每个 X a b f值转换为 r 类型的结果.令人高兴的是，只有一种可能的方法可以进行这种转换:调用 xCata使用与您开始传递的相同功能集。