Data structures not functions

Categories: Idioms

Sometimes the best way to implement a function is as a data structure. You can then implement a lightweight interpreter which "executes" the data structure.

There are many examples of this in Haskell code, but a simple one is algorithms which iterate until some condition is met. A good way to implement this is as an infinite stream of results, which is passed to an "interpreter" which selects which result is the most appropriate.

Rather than this loop:

squareRoot n = squareRoot' n (initialGuess n)
    where
        squareRoot' x
            | closeEnough x = x
            | otherwise     = squareRoot' (0.5 * (x + n/x))

write this:

squareRoot n = head . filter closeEnough $ squareRoot' n (initialGuess n)
 
squareRoot' n x = iterate (\x -> 0.5 * (x + n/x)) x

There are several advantages to using this approach :

• This is easier to test and debug, because the intermediate form doubles as an execution trace.
• There is a clean separation of responsibilities. If someone wants to use the algorithm with a different "close enough" test, or a better initial guess, it's easy to do.

Interestingly, if you implement this using standard list functions, such as head, filter and iterate, there may be no performance penalty. If the compiler uses a modern deforestation optimization, such as stream fusion, the intermediate data structure will be compiled away.

A more sophisticated (but not necessarily much more complex) application of this idiom is the GADT approach to prototyping monads.

You can also use functions not data structures.

User:AndrewBromage

Recent content is available under a simple permissive license.