Monday, 23 July 2012

Untying the Recursive Knot

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.

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete

Note: only a member of this blog may post a comment.