使用continuation在F#中处理树

Question

我试图理解延续是如何工作的,我在本书中遇到了这个例子,Tomas Petricek与Jon Skeet的真实世界功能编程.但这确实让我头疼,所以我必须要求一些详细的帮助..

type IntTree = 
    | Leaf of int
    | Node of IntTree * IntTree

let rec sumTreeCont tree cont =
  match tree with
  | Leaf(n) -> cont(n)
  | Node(left, right) -> 
      sumTreeCont left (fun leftSum ->
        sumTreeCont right (fun rightSum ->
          cont(leftSum + rightSum)))

好的,这就是我能够弄清楚自己......在第二个分支中,我们首先处理节点的左侧并传递一个lambda.此拉姆达将实例的封闭类具有两个字段,right: IntTree并且cont: (int -> 'a)这将是由基础案例被调用.但是,似乎"内在的lambda"捕获leftSum但我不太明白这一切是如何组合在一起的,我不得不承认,当我试图解决这个问题时,我有点头晕.

Answer 1

我认为克里斯蒂安的答案很好 - 延续传递风格实际上只是一个(不是那么)简单的机械转换,你在原始源代码上做.当您逐步执行此操作时,可能更容易看到:

1)从原始代码开始(这里,我将代码更改为每行只执行一次操作):

let rec sumTree tree =
   match tree with
   | Leaf(n) -> n
   | Node(left, right) -> 
       let leftSum = sumTree left
       let rightSum = sumTree right
       leftSum + rightSum

2)添加continuation参数并调用它而不是返回结果(这仍然不是尾递归).为了进行这种类型检查,我fun x -> x为两个子调用添加了延续,以便它们只返回总和作为结果:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) -> 
       let leftSum = sumTree left (fun x -> x)
       let rightSum = sumTree right (fun x -> x)
       cont (leftSum + rightSum)

3)现在,让我们改变第一个递归调用以使用延续传递样式 - 将身体的其余部分提升到延续:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) -> 
       sumTree left (fun leftSum ->
         let rightSum = sumTree right (fun x -> x)
         cont (leftSum + rightSum) )

4)并为第二次递归调用重复相同的事情:

let rec sumTree tree cont =
   match tree with
   | Leaf(n) -> cont n
   | Node(left, right) -> 
       sumTree left (fun leftSum ->
         sumTree right (fun rightSum -> 
           cont (leftSum + rightSum) ))

Answer 2

如果您首先考虑此表达式来计算树的总和,那么可能更容易理解:

let rec sumTree tree =
   match tree with
   | Leaf(n) -> n
   | Node(left, right) -> 
       sumTree left + sumTree right

此解决方案的问题在于,由于堆栈帧分配过多,它会溢出堆栈中的大型树.解决方案是使用确保递归调用处于尾部位置意味着您不能在调用之后执行任何操作(在上面的情况下,在递归调用之后执行添加).在这种情况下,编译器可以消除不必要的堆栈帧,从而避免溢出.解决这个问题的技巧是使用连续传递样式,如Tomas'和Jon的解决方案.如您所见,此处使用的continuation确保在递归调用之后不执行任何操作.

Answer 3

我在试图理解这一点的过程中制作了一张 Visio 绘图，我想我可以在这里分享它，以防它对其他人有所帮助。我意识到它最终可能会让某些人更加困惑，但对于视觉学习者（比如我），我觉得它让事情变得更清晰，绘制了一个例子来说明处理这样一棵树的方式。