23 July 2012

Here I present a couple of examples of the functional design pattern “untying the recursive knot”. I’ve found this useful in a couple of occasions, for instance when breaking apart mutually recursive functions. Material inspired by Jon Harrop’s excellent Visual F# to Technical Computing.

First, let’s look at a simple factorial implementation using direct recursion; We can break the direct recursive dependency by replacing the recursive calls with calls to a function argument; We have now broken the recursive knot! The functionality can be recovered by tying the recursive knot using the following y combinator; For example;This has given us extra power, we may for instance inject new functionality into every invocation without touching the original definition;Now for a more practical example when we have mutually recursive functions; We can break these functions apart using the same strategy as with fact’ above; Please note that the (declare …) form is no longer required. The functions are now entirely independent and could live in different namespaces.

Using the same y combinator above, we can get back to the original functionalty;A handy pattern to add to your functional toolbox.



Share this post

blog comments powered by Disqus