OCaml中的fold_tree [英] fold_tree in OCaml

问题描述

正如你所知，OCaml中有更高阶的函数，比如fold_left，fold_right，filter等。命名为fold_tree，类似fold_left / right，不在列表中，但在（二进制）树上。它看起来像这样：

  let rec fold_tree f a t = 
与$ b $匹配t Leaf  - > a | 
节点（l，x，r） - > f x（fold_tree f a l）（fold_tree f a r）;; 
  

其中树定义为：

  type'a tree = 
'a tree *'a *'a tree的节点| 
 Leaf ;; 
  

好的，这是我的问题：fold_tree函数如何工作？你可以给我一些例子，并用人类语言解释吗？ 解决方案

这里有一个风格建议，线。它使案件开始的地方更清晰。为了保持一致性，第一栏是可选的，但建议。

 键入'a tree = 
 | '一棵树*'a *'一棵树
 |的节点叶;; 
 
让rec fold_tree f a t = 
与
匹配t |叶 - > a 
 |节点（1，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 p>

可见， t 看起来像这样：

 
 5 
 / \ 
（）2 
 / \ 
（）（）
 

调用fold_tree，我们需要一个函数来组合这些值。根据 Node 情况下的用法， f 需要3个参数，所有相同类型的树并返回相同。我们会这样做：

  let f x l r = x + l + r ;; （*全部加在一起*）
 fold_tree f 1 t ;; 
  

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

As You may know, there are higher order functions in OCaml, such as fold_left, fold_right, filter etc.

On my course in functional programming had been introduced function named fold_tree, which is something like fold_left/right, not on lists, but on (binary) trees. It looks like this:

 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);;

Where tree is defined as:

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

OK, here's my question: how does the fold_tree function work? Could you give me some examples and explain in human language?

解决方案

Here's a style suggestion, put the bars on the beginning of the line. It makes it clearer where a case begins. For consistency, the first bar is optional but recommended.

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);;

---

As for how it works, consider the following tree:

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

With the type int tree.

Visually, t looks like this:

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

And calling fold_tree, we'd need a function to combine the values. Based on the usage in the Node case, f takes 3 arguments, all the same type of the tree's and returns the same. We'll do this:

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

It would help to understand what happens in each case. For any Leaf, a is returned. For any Node, it combines the stored value and the result of folding the left and right subtrees. In this case, we're just adding the numbers where each leaf counts as one. The result on the folding of this tree is 10.

这篇关于OCaml中的fold_tree的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！