如何将 Haskell 中的折叠函数与其他数据类型一起使用

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

一般准则（适用于在 ADT 上运行的所有函数，而不仅仅是折叠）将是 "one equation per constructor":

data MyType = Constructor1 Int | Constructor2 Float | Constructor3

myFunc :: MyType -> Int
myFunc (Constructor1 x) = ...
myFunc (Constructor2 y) = ...
myFunc Constructor3     = ...

此外，实现折叠函数的最正确方法是为您的类型声明一个 Foldable 实例。

Answer 2

正如 Willem Van Onsem 在 (now-deleted) 评论中指出的那样，您要实现的也称为 catamorphism。我在上写了一些关于我认为你可能称之为变质现象初学者的观点的文章。您可以非常机械地推导出类型的变形（或证明 none 可以存在）。如果您的类型有 N 个构造函数，则 fold 函数必须采用 N+1 个参数：您的类型的一个值，以及每个构造函数的一个函数。每个这样的函数在其对应的构造函数具有的每个字段中接受一个参数（或者，如果构造函数没有字段，则它接受一个普通值，您可以将其想象为一个 0 元函数），并且 returns 的值为任何类型的变形 returns.

文字比较复杂，我把上面链接的答案中的相关代码复制过来，作为范例：

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 使用与您开始传递的相同的一组函数。

如何将 Haskell 中的折叠函数与其他数据类型一起使用

How to use the fold function in Haskell with other datatypes

haskell

fold

algebraic-data-types