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

Question

我有一个类型 tree定义如下

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

我有一个函数来找到树的深度如下

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

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

Answer 1

您可以通过将函数转换为 CPS(继续传递样式)来轻松做到这一点。这个想法是，而不是调用 depth left ，然后根据这个结果进行计算，你调用 depth left (fun dleft -> ...) ，其中第二个参数是“一旦结果( dleft )可用时要计算的内容”。

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)

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

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

这里我们有三个延续闭包: (fun dleft -> depth right (fun dright -> k ...)) ，它只重用环境变量 right和 k , (fun dright -> ...) , 重用 k和现在可用的左侧结果 dleft , 和 (fun d -> d) ，初始计算，不捕获任何东西。

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

解构函数如下所示:

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是相互递归的。

现在仔细看看 ('a, 'b) cont ，这个数据类型是什么？这是一个 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 []
;;

列表是一个堆栈。我们这里实际上是对前面递归函数的调用栈的一个reification(转化为数据)，两种不同的case对应了两种不同的non-tailrec调用。

请注意，去功能化只是为了好玩。在实践中，CPS 版本很短，易于手工导出，相当容易阅读，我建议使用它。闭包必须在内存中分配， ('a, 'b) cont 的元素也是如此。 -- 尽管这些可能会更紧凑地表示。我会坚持使用 CPS 版本，除非有充分的理由去做更复杂的事情。