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.


Equational Reasoning Shopping List

April 10, 2008

Pure functional programming has the advantage that one can reason with it very like one does in mathematics. Specifically, if you know two expressions to be equal, they can be freely swapped. This underlies the use of inlining, sharing and the ability to replace any linear recursion with a fold, unfold, zip, etc. as appropriate.

As a first Haskell example, consider the following very-well-known optimization. Given code like

map f $ map g $ map h list

or in the more common style:

map f . map g . map h $ list

it appears naively that this will traverse the list three times: once to apply h, again to apply g, and finally a third time to apply f.

But because map, f, g and h are all pure functions, they can be replaced with something equivalent without changing the result of the code.

Consider an element of list, say x. After the three maps, it will have been replaced in the final list with f(g(h x))), or equivalently f . g . h $ x. So we should be able to replace the three maps with one that does the same thing:

map (f . g . h) list

And in fact GHC does precisely this.

Equational Rules
Following is a collection (and more are most welcome!) of rules for transforming your programs. I have written their equality with ==, though of course Haskell functions are not in Eq. I have written implication as –> and equivalence/double-implication as <–>.

map f . map g == map (f . g)
filter f . filter g     == filter (\x -> f x && g x)
                        == filter (liftM2 (&&) f g)
f . f == id --> filter (p . f) == map f . filter p . map f
filter (all p) . cartesianProduct == cartesianProduct . map (filter p)
filter p . concat == concat . map (filter p) == concatMap (filter p)

And now some concerning pairs and arrow combinators, Haskell translations of ones from Meijer et al.’s seminal paper:

fst . (f *** g) == f . fst
fst . (f &&& g) == f
-- and the obvious equivalents for snd and g.
fst . h &&& snd . h == id
fst &&& snd == id
(f *** g) . (h &&& j) == (f . h) &&& (g . j)
(f &&& g) . h == (f . h) &&& (g . h)
(f *** g) == (h *** j) <--> f == h && g == j
(f &&& g) == (h &&& j) <--> f == h && g == j

And more, translated from the same paper, for Either and the arrow combinators using it:

(f +++ g) . Left == Left . f
(f ||| g) . Left == f
-- and the obvious equivalents for g and Right
{- h strict -} --> (h . Left) ||| (h . Right) == h
Left ||| Right == id
(f ||| g) . (h +++ j) == (f . h) ||| (g . j)
{- f strict -} --> f . (g ||| h) == (f . g) ||| (f . h)
(f ||| g) == (h ||| j)  f == h && g == j
(f +++ g) == (h +++ j)  f == h && g == j

And finally the “Abides Law” tying the two together:

(f &&& g) ||| (h &&& j) == (f ||| h) &&& (g ||| j)

There are many more such rules, and if you have more to suggest I’d love to add them to the list.


April 9, 2008

I’ve accumulated a little backlog of Haskell thoughts looking for an outlet, and I’ve finally created this blog to hold them. Most of these will be papers or Haskell features that have coated the countryside in a fine film of my neurons.

Upcoming posts include:

  • A translation of Meijer et al.’s famous “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire” paper into Haskell, for those (like me) whose abstract notation buffers aren’t up to reading the original.
  • A collection (“shopping list”, to borrow a term) of equational rules for functional programming (e.g., foldr (:) [] == id). The goal is that you could look here for functions you’re using, and perhaps spot a rule that can simplify your code or improve your understanding. I’ve found these rules a great source of enlightening brain explosions,
  • PlainConfig, my upcoming text file configuration module for xmonad, designed to offer some configuration without the GHC dependency.

Those are in the order they occurred to me; they might appear in any order.