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

Stack Overflow用户

提问于 2018-10-06 03:04:45

回答 1查看 593关注 0票数 4

在两周内，我一直在用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从右向左)时，该如何做？有解决这些问题的技术吗？是否仍有可能以一种棘手的方式使用模式匹配以获得所需的结果？

fold

recursion

ocaml

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-10-07 00:03:41

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

首先是一个具体的版本。我们想知道一棵树是否倾斜，如果是，它有多少个节点。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不是“严格大于”，但这是故意的；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