haskell - 树折叠操作？

Question

我正在 Haskell 中学习一门类(class)，我们需要为以下定义的树定义折叠操作:

data Tree a = Lf a | Br (Tree a) (Tree a)

我似乎找不到任何有关“tfold”操作或它应该做什么的信息。任何帮助将不胜感激。

Answer 1

我一直认为折叠是一种用其他函数系统地替换构造函数的方法。因此，举例来说，如果您有一个自己动手的 List 类型(定义为 data List a = Nil | Cons a (List a))，则相应的折叠可以写成:

listfold nil cons Nil = nil
listfold nil cons (Cons a b) = cons a (listfold nil cons b)

或者，也许更简洁，如:

listfold nil cons = go where
    go Nil = nil
    go (Cons a b) = cons a (go b)

listfold 的类型为 b -> (a -> b -> b) -> List a -> b。也就是说，需要两个‘替换构造函数’；一个告诉如何将 Nil 值转换为 b，另一个用于 Cons 构造函数的替换构造函数，告诉 第一个值如何转换为 b code>Cons 构造函数(a 类型)应与 b 类型的值组合(为什么是 b？因为折叠已经被递归应用!)产生一个新的 b，最后是一个 List a 来应用整个 she-bang - 其结果为 b.

在您的情况下，tfold 的类型应该是 (a -> b) -> (b -> b -> b) -> Tree a -> b 通过类比推理；希望您能够从那里得到它!