在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))
;;

此函数不是尾递归的。有没有一种方法可以让我以尾递归的方式编写此函数？

- ppaul74

---

我相信如果你转换为延续传递风格，你就可以做到。 - Jeffrey Scofield

Answer 1

你可以通过将函数转换为 CPS（Continuation Passing Style）轻松地完成此操作。其想法是，不是调用 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计算结果。当传递一个Kleft时，eval会执行闭包(fun dleft -> ...)所做的操作，即对右子树进行递归调用depth。 eval和depth是相互递归的。

现在仔细看看('a, 'b) cont，这个数据类型是什么？它是一个列表！

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），两种不同情况对应着两种不同的非尾递归调用。

请注意，此处的defunctionalization只是为了好玩。在实践中，CPS版本短小，易于手动推导，相当容易阅读，并且我建议使用它。闭包必须在内存中分配，但 ('a, 'b) cont 的元素也必须在内存中分配 -- 虽然这些可能会表示得更紧凑。除非有非常充分的理由要做一些更复杂的事情，否则我建议坚持使用CPS版本。

- gasche

---

我认为Thomas的答案更好，因为它更清晰、更高效。 - Fabrice Le Fessant

这完全取决于发帖者是想学习如何使一个函数成为尾递归，还是此函数本身。 - gasche

Reynolds的去函数化CPS转换代码的好处在于，它可以更或多或少地机械地恢复常规（即仅具有一种递归调用）非尾递归函数的众所周知的尾递归累积版本，因为重新实现的连续体类型无疑是同构于列表类型。 - user593999

将某个函数转换为尾递归的原因之一是为了节省空间。虽然这不是唯一的原因，但通常是主要原因。我认为通过 CPS 将这个特定问题变为尾递归并不能节省空间。它似乎会将栈帧转换成函数，而且是 1:1 的比例。如果我在这方面有错误，请有人纠正我。 - Steve Rowe

@Steve，这个转换的复杂度与原始的非尾递归版本相同是正确的--确实，如果有一种通用技术可以减少任何递归函数的空间使用，那将会太好了！然而，我认为尾递归的一般动机更多地是为了节省栈空间，对于使用C/OS/硬件栈的实现，因为它比其他内存受到严格限制。在可以减少空间复杂度的情况下，实际上是在编写一个新的、不同的算法。 - gasche

话虽如此，去功能化的 CPS 版本有时有助于找到这个新的空间高效算法：你有时可以通过对 CPS 去功能化代码进行等式推理来推导出更好的版本。例如，如果你尝试在 length: 'a list -> int 函数上使用这种技术，你会注意到得到的 cont 类型与整数同构，并且直接使用整数可以给你常量内存的尾递归版本。 - gasche

Answer 2

在这种情况下（深度计算），您可以累加对(子树深度 * 子树内容)的配对，以获得以下尾递归函数：

let depth tree =
  let rec aux depth = function
    | [] -> depth
    | (d, Leaf _) :: t -> aux (max d depth) t
    | (d, Node (_,left,right)) :: t ->
      let accu = (d+1, left) :: (d+1, right) :: t in
      aux depth accu in
aux 0 [(0, tree)]

对于更一般的情况，您确实需要使用Gabriel描述的CPS转换。

- Thomas

---

确实，这种算法的表达更为简洁。你可以将这个算法理解成两种技术的组合：使用列表是深度优先遍历的常规尾递归化（广度优先遍历使用下一个邻居的FIFO队列，而深度优先遍历使用LIFO列表）; 而线索参数“depth”是一个隐藏状态单子，用于累积有关结果的信息--参考文献也可以完成工作。 - gasche

Answer 3

有一个简洁通用的解决方案，使用 fold_tree 和 CPS - 连续传递样式：

let fold_tree tree f acc =
  let loop t cont =
    match tree with
    | Leaf -> cont acc
    | Node (x, left, right) ->
      loop left (fun lacc ->
        loop right (fun racc ->
          cont @@ f x lacc racc))
  in loop tree (fun x -> x)

let depth tree = fold_tree tree (fun x dl dr -> 1 + (max dl dr)) 0

- Viet