Recursion Fail

April 11, 2008

It’s been a Haskell programming rule of mine for a long time that explicit recursion is an admission of failure. First, linear recursions have already been captured in one of the Prelude (or Data.List) functions. Second, recursions or iterations over a data structure are almost always either fmap or one of the Data.Foldable functions. Third, the list monad (and list comprehensions) capture a common recursion pattern, one found especially in path-finding, alpha-beta AI, and other try-every-path problem spaces.

If you’re recursing, and lists are involved, the recursion pattern has already been captured in a Prelude or Data.List function. map, the fold*s, the scan*s, filter, find, unfoldr and group(By) cover, I think, every loop I’ve ever written in an imperative language.
The dynamic “scripting” languages like Perl and Python have had foreach loops for years, to cover the most common case of looping over every element of an array. Java 1.6 and C# have this too. That’s a handy bit of syntactic sugar, but it is only a weak replacement for map, and doesn’t help at all for any of the others.

Programmers new to FP, including me when I was learning Haskell, often find it hard to think in terms of folds and maps. So go ahead, write the explicitly recursive version. But when you’re done, replace it with the appropriate library function. In time, you won’t need to write it down any more and will think of what you would write, recognize it as one of these higher-order functions, and write that down instead. Eventually, you’ll think in the folds and maps directly.

What about when you’re not working on lists? Take another common structure, trees. Or any other data structure, really. Consider this binary tree implementation:

data Tree a = Empty | Node a (Tree a) (Tree a)

It’s fairly obvious that we could map a function over the tree. This common pattern is represented by the typeclass Functor. Functors represent “things which can be mapped over”, or containers to whose contents we might like to apply a function. Note that any Monad is also a Functor, though Haskell 98 does not enforce this. Some existing, handy Functors: Maybe, lists, functions ((->) a), tuples (a,), Either a, Map k.
The Functor typeclass contains a single function, fmap :: (Functor f) => (a -> b) -> f a -> f b. It turns an ordinary function into one “inside the functor”. For our tree:

instance Functor Tree where
    fmap _ Empty        = Empty
    fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)

It’s similar in spirit to map over lists, and in fact fmap = map for lists.

Writing the instance for the Functor or Foldable type classes, which you only do once, has huge maintenance and conciseness advantages over writing the explicit recursion in even two places. That would be true of a treeMap function for a tree that isn’t a Functor. The advantage of the typeclasses is that they provide a standard interface common to many libraries.

Finally, many seemingly complex recursion patterns, especially in the path-finding and alpha-beta AI spaces can be written in a list comprehension, or (if you prefer) in list monad do-notation.