在 Ocaml 中查找树深度的尾递归函数

问题描述

我有一个类型 tree 定义如下

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)

这是一个众所周知的技巧，可以使任何函数尾递归.瞧，这是尾声.

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

包中的下一个众所周知的技巧是去功能化"CPS 结果.延续((fun dleft -> ...) 部分)作为函数的表示很简洁，但您可能想看看它作为数据的样子.所以我们用一个数据类型的具体构造函数替换这些闭包中的每一个，它捕获其中使用的自由变量.

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

解函数后的函数如下所示:

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 和 depth 是相互递归的.

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 中查找树深度的尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！