Tree processing in F # using continuations

Question

I am trying to understand how continuations work. I have this example that I found in the book "Real World Functional Programming" by Thomas Petrichek with John Skeet. But actually my head is spinning, so I have to ask for help.

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))) 

It's good that I was able to figure it out myself ... In the second branch, we first process the left side of the node and pass the lambda. This lambda will create a closure class with two right: IntTree fields right: IntTree and cont: (int -> 'a) , which will be called by the base case. But then it also seems that the “inner lambda” captures the leftSum , but I don’t quite understand how it all fits together, I have to admit that I have a little dizziness when I try to figure it out.

Answer 1

I think the Christian answer is good - the continuation of the walkthrough style is just (not so) a simple mechanical transformation that you do in the source code. It may be easier to see when you do this step by step:

1) Start with the source code (here I change the code to only one operation per line):

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

2) Add a continuation parameter and call it instead of returning the result (this is still not tail recursive). To perform this type checking, I added a continuation of fun x -> x for both subheadings, so that they simply return the sum as a result:

 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) Now we change the first recursive call to use the continue transmission style - raise the rest of the body to continue:

 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) And repeat the same for the second recursive call:

 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

You may find it easier to understand if you first consider this expression to calculate the sum of a tree:

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

The problem with this solution is that it overflows the stack for large trees due to the excessive distribution of stack frames. The solution is to use make sure that the recursive call is in the tail position, which means that you cannot perform any operation after the call (in the above case, the addition is done after the recursive calls). In this case, the compiler can eliminate unnecessary stack frames and thus avoid overflow. The technique to solve this problem is to use the continuation style, as in the solution of Tomas and Jon. As you can see, the extensions used here ensure that no operations are performed after recursive calls.

Answer 3

I made a Visio drawing, trying to figure it out, I thought I could share it here if it helps someone else. I understand that this can be confusing for some, but for viewers (like me). I feel this made it easier to draw an example of what it might look like for processing a tree like this.