使用continuation将二进制递归转换为尾递归

Question

当我正在阅读Programming F#书时,我在第195页找到了示例代码段,如下所示:

type ContinuationStep<'a> =
  | Finished
  | Step of 'a * (unit -> ContinuationStep<'a>)

let iter f binTree =
  let rec linearize binTree cont =
    match binTree with
    | Empty -> cont()
    | Node(x, l, r) ->
      Step(x, (fun () -> linearize l (fun() -> linearize r cont)))

  let steps = linearize binTree (fun () -> Finished)

  let rec processSteps step =
    match step with
    | Finished -> ()
    | Step(x, getNext)
      -> f x
        processSteps (getNext())

  processSteps steps

通过使用continuation,遍历二进制的二进制递归已经转换为尾递归函数processSteps.我的问题是,另一个函数linearize似乎是非尾递归的.这是否意味着即使使用continuation,我们也无法将二进制递归完全转换为尾递归？

Answer 1

linearize 是尾递归的:你不需要从递归调用返回来继续计算.

fun () -> linearize l (fun() -> linearize r cont)

不打电话linearize.计算暂停直到processSteps调用getNext ().

Answer 2

该示例有点微妙,因为它不使用普通的continuation,而是构建一个可以逐步评估的结构.在通常进行递归调用的位置,它返回一个Step包含您(递归)调用的函数的值.

在第二种情况下,linearize函数返回一个Step包含一个将linearize递归调用的函数,但它不会立即进行递归调用.因此该函数不进行递归调用(它只存储递归引用).

它才有意义考虑程序是否是尾递归,当你看processSteps,因为那不实际的循环-这是尾递归,因为它运行一个Step由Step不保持堆栈空间的每一个Step.

如果你想构建一个列表而不是一堆懒惰的步骤,那么你必须linearize立即在延续中进行递归调用:

let rec linearize binTree cont = 
  match binTree with 
  | Empty -> cont [] 
  | Node(x, l, r) -> 
      linearize l (fun l -> linearize r (fun v -> cont (x::v)))

这与前一个函数基本相同,但它实际上调用linearize而不是构建Step包含将调用的函数linearize.