[Haskell-cafe] Levels of recursion

[Andrew Wagner]

  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
think about it.

  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.

  So, a couple of questions to ponder about this: Is this unique to
Haskell, or could the same be said about any functional language? How
can we teach this better to newbies? Most of what I see in the
tutorials is "Higher order functions accept as parameters and/or
return other functions. Here's some examples: <explanation of map>,
<explanation of foldr>. Moving on, ..."   But clearly, this is
something important, and I think we can do a better job of teaching
it. Suggestions?