尾递归函数,用于在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 -> ...),其中第二个参数是"一旦result(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)

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

袋中的下一个众所周知的技巧是"去功能化"CPS结果.(fun dleft -> ...)作为函数的continuation(部分)的表示是整洁的,但您可能希望看到它看起来像数据.因此,我们用数据类型的具体构造函数替换每个闭包,捕获其中使用的自由变量.

在这里,我们有三个封延续:(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

defunctorized函数如下所示:

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并将其应用于leaves(k 0),而是构建了一个类型的数据('a, int) cont,需要稍后对其eval进行计算以计算结果.eval当它被传递时Kleft,执行闭包(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 []
;;

列表是一个堆栈.我们这里所拥有的实际上是前一个递归函数的调用堆栈的具体化(转换为数据),两种不同的情况对应于两种不同类型的非tailrec调用.

请注意,defunctionalization只是为了好玩.在实践中,CPS版本很简单,易于手工派生,相当容易阅读,我建议使用它.闭包必须在内存中分配,但是元素也是如此('a, 'b) cont- 虽然那些可能更紧凑地表示.我会坚持使用CPS版本,除非有很好的理由去做更复杂的事情.

Answer 2

在这种情况下(深度计算),您可以累加成对(subtree depth*subtree content)以获得以下尾递归函数:

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转换.