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

Question

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

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

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

现在假设信息I可以在二叉树上从左到右计算。当我说从左到右时，意味着可以从根到叶计算信息I，而无需向后计算。

更清楚地说，我们想要的信息I只是“二叉树的节点数”。那么这个信息的好处是，当我们到达所有叶子时，我们就会得到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 是:“二叉树具有以下特性:对于每个节点，其左子树中的节点数严格优于其右子树中的节点数子树”。如果我们想在线性时间内解决这个问题，那么我们需要从叶子开始并递归地扩展到顶部(请注意，我不一定想要问题的解决方案)。

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

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

Answer 1

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

首先是具体版本。我们想知道一棵树是否是左倾的，如果是的话，它有多少个节点。 int 选项 可以很好地表示这一点，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 并不是“严格大于”，但这是故意的；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

这是树构造函数上模式匹配的替代方法。