Andrew Wagner wagner.andrew at gmail.com
Wed Jan 31 14:35:30 EST 2007

```  I won't speak for anyone else, but I remember when recursion first
"clicked". It was in a 400-level data structures and algorithms class.
I had already done a fair amount of chess programming (which of course
does a massive amount of recursion), but it still seemed a bit magical
to me. When the professor pointed out that you simply have to assume
that the recursive call will work, and then the whole recursive
definition will, a light bulb went on.

Of course, once I started learning haskell, such "aha!" moments
quickly became a way of life. Things like map, foldr, and the lazy
definition of fibs all made me stop and think for a while, and when I
understood them, I was better for it.

I had a sort of interesting moment like this last night. In hacking
on some code, I wrote the following function:

combine :: [Int] -> [Int] -> [[Int]]
combine [] _ = []
combine (x:xs) ys = (take x ys) : (combine xs (drop x ys))

To me, this is recursion. Define your base case, take care of one
part of the problem, and then call yourself recursively to take care
of the rest. This is how I was taught recursion, and this is how I

Now for the fun part. A much more experienced haskeller told me he
preferred to write it like this:

combine' :: [Int] -> [Int] -> [[Int]]
combine' xs ys = snd \$ mapAccumL aux ys xs
where aux ys n = (b,a)
where (a,b) = splitAt n ys

Ack! Where'd the nice "base-case, take a chunk, recursively do the
rest" pattern go? Suddenly, recursion isn't so simple when it's done
using composition and higher-order functions which abstract recursive
patterns.

Like I said, I'm familiar with map, foldr, etc. But this is the
first time it's dawned on me that I need to think in more general
recursive patterns like this instead of simple, raw recursion. That
map and foldr aren't JUST a nice way of doing things to a little list,
but they are recursive operators, building blocks that I need to use
as fluently as anything else.

I suspect I'm not alone, though of course I could be wrong. But I
would bet that a significant difference between newbies and more
experienced Haskell programmers is the degree to which they can think
in this composition/HOF way. Where the beginner wants to program using
raw, simple recursion, the more experienced sees an opportunity to
apply an abstraction.