OCaml中的fold_tree

Question

您可能知道,OCaml中有更高阶的函数,例如fold_left,fold_right,filter等.

在我的函数式编程课程中引入了一个名为fold_tree的函数,它类似于fold_left/right,不在列表上,而是在(二元)树上.它看起来像这样:

 let rec fold_tree f a t = 
  match t with
    Leaf -> a |
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

树被定义为:

type 'a tree = 
  Node of 'a tree * 'a * 'a tree | 
  Leaf;;

好的,这是我的问题:fold_tree函数如何工作？你能给我一些例子并用人类语言解释吗？

Answer 1

这是一个样式建议,把条形图放在行的开头.它使案件开始时更清楚.为保持一致性,第一个栏是可选的,但建议使用.

type 'a tree = 
  | Node of 'a tree * 'a * 'a tree
  | Leaf;;

let rec fold_tree f a t = 
    match t with
      | Leaf -> a
      | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

至于它的工作原理,请考虑以下树:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));;

随着类型int tree.

在视觉上,t看起来像这样:

   5
  / \
 ()  2
    / \
   () ()

并且调用fold_tree,我们需要一个函数来组合这些值.根据Node案例中的用法,f取3个参数,树的所有相同类型并返回相同的参数.我们会这样做:

let f x l r = x + l + r;; (* add all together *)
fold_tree f 1 t;;

这将有助于了解每种情况下会发生什么.对于任何Leaf,返回a.对于任何Node,它结合了存储的值和折叠左右子树的结果.在这种情况下,我们只是添加每个叶子计为一个的数字.折叠这棵树的结果是10.

Answer 2

我们来看一个示例树.

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf))

折叠操作的一般定义是您可以通过树中的任何位置的函数替换构造函数.

general_fold_tree node leaf t =
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf)

node是构建了一个功能的东西从左边的东西,一个元素,一个正确的东西,就像Node是从一个左子树,节点的内容和右子树构成一个树的构造函数.leaf是一个常量,匹配Leaf常量构造函数.

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b =
  let recurse t = general_fold_tree node leaf t in
  match t with
  | Node (l, x, r) -> node (recurse l) x (recurse r)
  | Leaf -> leaf

请注意,函数的类型与类型定义的类型匹配,除了在类型定义描述构建的情况下'a tree,fold函数描述了any的构建'b.

看起来很像普通折叠的操作仍被称为折叠.例如,在列表上,List.fold_right根据上面的定义是一般折叠; List.fold_left是一种变形,它fold_left以相反的方式应用函数(相当于反向+ fold_right+反向,虽然它更清晰,更有效).

你自己fold_tree是这个一般折叠的一个简单变体,其中节点函数的参数与构造函数的顺序不同:

let equrts_fold_tree f a t =
  let node l x r = f x l r in
  general_fold_tree node a t