我有一个类型 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))
;;
这个函数不是尾递归的。有没有办法让我以尾递归的方式编写这个函数?
最佳答案
您可以通过将函数转换为 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 版本,除非有充分的理由去做更复杂的事情。
关于tree - 尾递归函数在 Ocaml 中查找树的深度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9323036/