recursion - OCaml fold_tree 和令人困惑的递归

Question

如果有人可以帮助我理解这段代码：

let rec fold_tree f (T(x,l))=
  f x (map (fold_tree f) l);;

这个怎么运作？我的意思主要是递归。

Answer 1

我想您的数据类型声明如下：

type 'a ntree = T of 'a * 'a ntree list;;

现在弄清楚它的最好方法是：
1-看一下它的类型签名，

val fold_tree : ('a -> 'b list -> 'b) -> 'a ntree -> 'b = <fun>

2 - 根据类型签名编写测试用例，

let test_rtree = T("a", [ T("b", []) ; T("c", [ T ("f", [])]) ; T("d", [])])  
in fold_tree (List.fold_left (^)) test_rtree;;
- : string = "abcfd"

3 - 拿一张纸和一支铅笔，尝试重现测试用例的输出。

Answer 2

如果我正在为树编写折叠函数，我会尝试定义一些 type ('a -> 'b -> 'b) -> 'a tree -> b -> b。也就是说，要折叠的函数将从树节点获取值和累加值，并产生新的累加值。（那么有趣的问题是访问节点的顺序。）

在此fold_tree，要折叠的函数有 type ('a -> 'b list -> 'b)。也就是说，它需要一个累积值列表而不是单个值。这使得它使用起来有点笨拙。

但是，它确实在时尚之后起作用。本质上，定义在散文中说明了以下内容：对于叶子，调用您的函数f，将节点值x和空列表传递给它。对于非叶子，首先在所有子树上递归调用自己，然后调用f传递节点值和递归调用结果列表的函数。

我希望这有帮助。