尾递归函数在Ocaml中查找树的深度 [英] Tail recursive function to find depth of a tree in Ocaml

问题描述

我有一个类型为的树，定义如下：



I have a type tree defined as follows

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

我有一个函数来查找树的深度如下所示：

I have a function to find the depth of the tree as follows

let rec depth = function 
    | Leaf x -> 0
    | Node(_,left,right) -> 1 + (max (depth left) (depth right))
;;

这个函数不是尾递归的。有没有办法让我用尾递归的方式编写这个函数？

This function is not tail recursive. Is there a way for me to write this function in tail recursive way?

推荐答案

通过将函数转换为CPS（Continuation Passing Style），可以简单地完成此操作。这个想法是，不是调用 depth left ，然后根据这个结果计算东西，而是调用 depth left（fun dleft - > .. 。），其中第二个参数是一旦结果（ dleft ）可用时计算什么。

You can trivially do this by turning the function into CPS (Continuation Passing Style). The idea is that instead of calling depth left, and then computing things based on this result, you call depth left (fun dleft -> ...), where the second argument is "what to compute once the result (dleft) is available".

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> k 0
    | Node(_,left,right) ->
      depth left (fun dleft ->
        depth right (fun dright ->
          k (1 + (max dleft dright))))
  in depth tree (fun d -> d)

这是一个众所周知的技巧，可以使任何函数的尾递归。 Voilà，这是尾巴。

This is a well-known trick that can make any function tail-recursive. Voilà, it's tail-rec.

下一个众所周知的技巧是去功能化CPS的结果。 continuations（（fun dleft - > ...） parts）的表示方式是简洁的，但您可能希望看到它看起来像是数据。所以我们用一个数据类型的具体构造函数替换每个闭包，捕获它中使用的自由变量。

The next well-known trick in the bag is to "defunctionalize" the CPS result. The representation of continuations (the (fun dleft -> ...) parts) as functions is neat, but you may want to see what it looks like as data. So we replace each of these closures by a concrete constructor of a datatype, that captures the free variables used in it.

这里我们有三个连续闭包：（fun dleft - > depth right（fun dright - > k ...）），它只重用环境变量 right 和 k ，（fun dright - > ...），它们重用 k 和现在可用的结果 dleft 和（fun d - > d） ，最初的计算，不捕获任何东西。

Here we have three continuation closures: (fun dleft -> depth right (fun dright -> k ...)), which only reuses the environment variables right and k, (fun dright -> ...), which reuses k and the now-available left result dleft, and (fun d -> d), the initial computation, that doesn't capture anything.

type ('a, 'b) cont =
  | Kleft of 'a tree * ('a, 'b) cont (* right and k *)
  | Kright of 'b * ('a, 'b) cont     (* dleft and k *)
  | Kid

defunctorized函数如下所示：

The defunctorized function looks like this:

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> eval k 0
    | Node(_,left,right) ->
      depth left (Kleft(right, k))
  and eval k d = match k with
    | Kleft(right, k) ->
      depth right (Kright(d, k))
    | Kright(dleft, k) ->
      eval k (1 + max d dleft)
    | Kid -> d
  in depth tree Kid
;;

不是构建函数 k 并应用它在叶子上（ k 0 ），我创建了一个类型为（'a，int）cont 的数据，需要稍后 eval 来计算结果。 eval ，当它通过 Kleft 时，做什么闭包（fun dleft - > ; ...）在做，也就是递归地在右子树上调用 depth 。 eval 和深度是相互递归的。

Instead of building a function k and applying it on the leaves (k 0), I build a data of type ('a, int) cont, which needs to be later evaluated to compute a result. eval, when it gets passed a Kleft, does what the closure (fun dleft -> ...) was doing, that is it recursively call depth on the right subtree. eval and depth are mutually recursive.

硬在（'a，'b）cont ，这个数据类型是什么？这是一个列表！

Now look hard at ('a, 'b) cont, what is this datatype? It's a list!

type ('a, 'b) next_item =
  | Kleft of 'a tree
  | Kright of 'b

type ('a, 'b) cont = ('a, 'b) next_item list

let depth tree =
  let rec depth tree k = match tree with
    | Leaf x -> eval k 0
    | Node(_,left,right) ->
      depth left (Kleft(right) :: k)
  and eval k d = match k with
    | Kleft(right) :: k ->
      depth right (Kright(d) :: k)
    | Kright(dleft) :: k ->
      eval k (1 + max d dleft)
    | [] -> d
  in depth tree []
;;

列表是堆栈。我们在这里实际上是前一个递归函数调用堆栈的一个实例（转换为数据），其中两种不同的情况对应于两种不同类型的非tailrec调用。

And a list is a stack. What we have here is actually a reification (transformation into data) of the call stack of the previous recursive function, with two different cases corresponding to the two different kinds of non-tailrec calls.

注意，去功能化只是为了好玩。在实践中，CPS版本很短，易于手工推导，而且易于阅读，我建议使用它。闭包必须在内存中分配，但（'a，'b）cont 的元素也是如此，尽管这些元素可能会更紧凑。我会坚持CPS版本，除非有很好的理由去做更复杂的事情。

Note that the defunctionalization is only there for fun. In pratice the CPS version is short, easy to derive by hand, rather easy to read, and I would recommend using it. Closures must be allocated in memory, but so are elements of ('a, 'b) cont -- albeit those might be represented more compactly`. I would stick to the CPS version unless there are very good reasons to do something more complicated.

这篇关于尾递归函数在Ocaml中查找树的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！