您可以通过将函数转换为 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
and k
, (fun dright -> ...)
,它重用了k
以及现在可用的左结果dleft
, and (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
and 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 调用。
请注意,取消功能只是为了好玩。实际上,CPS 版本很短,很容易手动导出,也很容易阅读,我建议使用它。闭包必须在内存中分配,但元素也是如此('a, 'b) cont
-- 尽管这些可能会更紧凑地表示。我会坚持使用 CPS 版本,除非有充分的理由去做一些更复杂的事情。