When a book is packed with concepts and information it’s very easy to gloss over something that in retrospect is very interesting. I often skim back over things I’ve already read hoping some of the new information I’ve accumulated will lead to deeper insights and interesting discoveries. “Untying the recursive knot” from F# for Scientists is one such concept I don’t believe I was sufficiently fluent enough in functional programming to glean its power. Let’s have a look.
Recursive Functions
The factorial function is a pretty standard function for introducing the concept of recursion to beginning functional programmers.
let rec factorial = function
| 0 -> 1
| n -> n * factorial (n – 1)
The rec keyword allows us to recursively call our factorial function passing in a number 1 less than the current call. The factorial function is a perfectly good function that accomplishes its assigned task, hence
> factorial 5;;
val it : int = 120
but as functional programmers we’re not so interested in standalone functionality as the ability to compose simple functions into more complex ones. We have no way to intercept the recursion and plug in a piece of custom functionality.
So how can we untie this recursive knot?
Higher Order Continuations
We can rewrite our factorial function to accept the function it should call next.
//val factorial : (int -> int) -> int -> int
let factorial factorial = function
| 0 -> 1
| n -> n * factorial(n – 1)
And now we need a way to jumpstart the recursion.
//val y : ((’a -> ‘b) -> ‘a -> ‘b) -> ‘a -> ‘b
let rec y f x =
f (y f) x
The y combinator will continue to generate a continuation for us as long as we ask for one. Applying y to our factorial function gives us the answer we expect
> y factorial 5;;
val it : int = 120
except now we’re able to insert some custom functionality right into the middle of the recursion.
> y (factorial >> fun f n -> printf “%d\n” n; f n) 5;;
5
4
3
2
1
0
val it : int = 120
Pretty neat! Instead of each function having its own proprietary recursion, we’ve made y our recursive combinator, and all other functions are responsible for playing nicely with it or risk being excluded from the fun.