I received a comment in my article about discriminated unions that the recursive function `calcLength`

was not tail call optimized.

Yikes I need to fix that, I had heard of tail call optimization but I had not really looked at it at this point.

Well, how hard could it be anyway, so I did some searching and looked at some articles. Recursion and Tail-recursion in F# by Karlkim Suwanmongkol, Tail calls in F# – MSDN Blogs and What is tail-recursion? – StackOverflow

After reading these articles, I realized that my recursive calls needed to be made as a single unit. A simple call with a simple return value. I needed a `Tail Call`

, a sub routine call performed as the last action of a function. A tail call to a recursive function can be optimized by the the F# into a loop.

That sounds simple enough, and for a seasoned expert I’m sure it is.

Here is the original stating point code:

let rec calcLength x = match x with | Circle (_,r) -> System.Math.PI * r * 2. | Ellipse (_,r1,r2) -> System.Math.PI * 2. * sqrt( (r1 * r1 ) + (r2 * r2 ) / 2.) | Square (_, w,_) -> w * 4. | MultiPrimitive [] -> 0. | MultiPrimitive (head::tail) -> calcLength (MultiPrimitive tail) + (calcLength head)

There are are two problems with the code above, the first is that there are two calls to `calcLength`

. And the second is that even if there was only one call, the plus operator ties the final call to `calcLength`

to another value and so it would not be considered a tail call.

To make this function conform to the needs of tail call optimization it is necessary to change the last match for MultiPrimitive such that there is a single call to `calcLength`

| MultiPrimitive (head::tail) -> calcLength ...

So the solution is a simple as that, the trick is in filling in the dots.

Introducing CPS or Continuation Passing Style. This is a common pattern used in F# ( and other functional languages). The pattern is useful for tail call optimization because it allows computations to be passed along for somebody else to do. Using this pattern can allow a recursive function call to be simplified ( actually it looks more complex, but to compiler its simplified ) such that it qualifies for tail call optimization. In our case we need to call `calcLength`

once and pass all the other calculations along to be done later.

Well in order to pass off work, a function parameter should be included as an argument to `calcLength`

. From the examples I’ve seen using the pattern it is often named `cont`

for continuation function.

Starting with just the non recursive part, here is how the function now looks:

let rec calcLength x cont = match x with | Square (_, w,_) -> cont (w * 4.) let r = calcLength (Square( (10.,10.), 10., 45. )) (fun x -> x )

When square is matched, instead of just returning the result, it passes the result as a parameter to cont, then cont returns the result.

Diving in, here is `calcLength`

using CPS

let rec calcLength x cont = match x with | Circle (_,r) -> cont (System.Math.PI * r * 2.) | Ellipse (_,r1,r2) -> cont (System.Math.PI * 2. * sqrt( (r1 * r1 ) + (r2 * r2 ) / 2.)) | Square (_, w,_) -> cont (w * 4.) | MultiPrimitive [] -> cont 0. | MultiPrimitive (h::t) -> calcLength h (fun hResult -> calcLength (MultiPrimitive t) (fun tResult -> cont (hResult + tResult)))

The base cases are the same as the `Square`

example above, they just pass there calculation result into the continuation method which intern returns the result.

The recursive part now calls `calcLength`

once just for the head. And it composes a function that computes the tail result and adds it to the head result. This composed function is passed with the head as the cont function.

Like the base cases, the composed function eventually ends up calling cont with the head result and the tail result added. But the main point is that every call to `calcLength`

is in the simple form as described above.

One tip I was given by Tomas Petricek was that if you are using Visual Studio, you need check `Generate tail calls`

in your project settings in order to get the tail calls optimized.

### Summing up

To be honest, looking at this final code causes me a double take, it is not nearly as simple as the original. Would this be a better candidate for a loop and a mutable variable? Personally I like code to be as simple as possible for the reader. However, it may be I’m just too new to F#, perhaps after some time you just instantly recognise this pattern and immediately understand what’s going on.

I would love to hear your comments and thoughts about this.

Vasily Kirichenko says

You can make CPS style code make more “linear” by using Continuation computation expression. You can find one of the implementations in FSharpx library here https://github.com/fsprojects/fsharpx/blob/master/src/FSharpx.Core/ComputationExpressions/Continuation.fs

I rewrite your function with it, take a look: https://gist.github.com/vasily-kirichenko/dca54aed344f05fc1ae3

Michael Coxeter says

Wow thanks Vasily,

That reads so much better. F# is one surprise after another, how deep does the rabbit hole go?

Chris Ma says

As a slight alternative to CPS, you can use an auxiliary function that accepts an extra parameter that holds the currently computed value so far:

https://gist.github.com/anonymous/d8e0e151c35f8784f895#file-gistfile1-txt

Note: I did cheat a little bit as I didn’t actually explicitly create the auxiliary function but just used one provided by the language

Michael Coxeter says

Thanks Chris,

Not a cheat at all, I like that you used List.fold!

I’m finding, while learning F#, its a good practice to just check to see if the framework has the function your about to write. It often does.

Your approach uses fold to handle the traversing the tree, you don’t even see the head and tail being used. I like that, is seems more decoupled.

Would this approach be considered the most idiomatic?

I guess you have to be careful and check that the function you call plays well with recursion and that you still get the tail call optimization.

Great comment!

Thanks

Chris Ma says

Yeah, I would say it’s more idiomatic, considering it’s easier to understand then CPS and likely faster as well.

Here’s a stackoverflow post about implementing foldback using continuations, one of the post has a link to another post where they did a timed comparison of another simple algorithm in CPS vs non-CPS form.

Chris Ma says

Ooops, forgot the link:

http://stackoverflow.com/questions/12680085/why-list-foldback-is-implemented-via-mutable-array-and-not-via-continuation