两种不同类型的 OCaml 递归函数

Question

在两周内，我一直在用 OCaml 编写一些简单的程序。我注意到当我们使用递归结构 T 并且我们希望在 T 上获得信息 I 然后根据信息 I 我们有两种类型的递归函数。

为简单起见，我们假设 T 是一棵二叉树。所以我将使用以下类型：

type 'a tree = Empty | 'a * 'a tree * 'a tree

现在假设信息I可以在二叉树上从左到右计算。当我说从左到右时，这意味着信息 I 可以从根到叶计算而不会倒退。

为了更清楚，让我们假设我们想要的信息 I 只是 "the number of nodes of the binary tree"。然后这个信息的好处是，当我们到达所有叶子时，我们得到 I，所以我们从左到右，从根开始，递归地扩展到左子树和右子树，最终情况是我们到达叶子的时候。

所以我们有：

let rec nodes = function
    |Empty -> 0 (*it's ok we are done here*)
    |Node(_,l,r) -> 1 + nodes l + nodes r

非常棒的是，当信息可以从左到右计算时，OCaml 的模式匹配是一个非常强大的工具，信息 I 可以以简单的方式计算。所以更一般地说，我们有：

let rec get_information = function
    | Empty     -> (*here we are done so we return a constant value*)
    |Node(_,l,r)-> (*here we apply recusrively the function to the left and right tree*)

现在我的问题来了。假设I是一个不能从左到右计算而是从右到左计算的信息。所以这意味着要获取信息 I 我们需要从树的叶子开始并递归地扩展到顶部，只有当我们到达二叉树的根时我们才完成（所以最终情况是当我们到达二叉树的根而不是叶子时）。

例如，假设信息 I 是："the binary tree has the propriety that for every node the number of nodes in his left subtree is strictly superior to the number of nodes in his right subtree"。如果我们想在线性时间内解决这个问题，那么我们需要从叶子开始，递归地扩展到顶部（注意，我不一定想要问题的解决方案）。

所以对我来说，当 I 是从右到左的信息（它需要从叶子开始并延伸到顶部）时，编写一个获取信息 I 的函数是很棘手的.相反，当信息是从左到右的信息时，模式匹配是完美的。

所以我的问题是当我们需要写一个获取信息I的函数时（当I是从右到左时）怎么办？是否有解决此类问题的技术？是否仍然可以以一种棘手的方式使用模式匹配以获得所需的结果？

Answer 1

模式匹配对于编写这两种函数都很有用。也可以使用称为折叠的高阶函数。

首先，一个具体的版本。我们想知道一棵树是否左倾，如果是，它有多少个节点。 int option 将很好地表示这一点，None 表示任何非左倾树。

type 'a tree = Empty | Branch of 'a * 'a tree * 'a tree

let rec tree_info = function
  | Empty -> Some 0
  | Branch (_, l, r) ->
    match tree_info l, tree_info r with
    | Some x, Some y when x >= y -> Some (x + y + 1)
    | _ -> None

let is_left_leaning tree =
  match tree_info tree with
  | Some _ -> true
  | None -> false

（请注意条件 x >= y 不是 'strictly greater than'，但这是故意的；x > y 是一个糟糕的选择。我将找出原因作为练习。）

我们也可以用一种称为右折叠的操作来表达这种函数风格。对于此操作，为被折叠的数据类型的每个构造函数提供一个值：在构造函数出现的每个地方，折叠操作将使用该值来计算折叠的结果：

let rec foldr empty branch = function
  | Empty -> empty
  | Branch (x, l, r) ->
    branch x (foldr empty branch l) (foldr empty branch r)

注意empty值和Empty构造函数有相同的元数，branch值和Branch构造函数有相同的元数，对应参数类型。这是正确折叠的特征。

给定foldr，我们可以很容易地定义map:

let map f tree =
  foldr Empty (fun x l r -> Branch (f x, l, r)) tree

当然，'tree_info':

let tree_info tree =
  foldr
    (Some 0)
    (fun _ l r ->
       match l, r with
       | Some x, Some y when x >= y -> Some (x + y + 1)
       | _ -> None)
    tree

这是 tree.

构造函数上模式匹配的替代方法

两种不同类型的 OCaml 递归函数

Two different types of OCaml recursive functions

recursion

ocaml

fold