[Haskell-cafe] Levels of recursion

[Cale Gibbard]

On 31/01/07, Andrew Wagner <wagner.andrew at gmail.com> wrote:
>   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?

This is absolutely correct. I suppose I was lucky in that it was
probably my first epiphany of functional programming, and came before
I'd really learned much Haskell at all. I somehow determined that
working on understanding the translation from loops in the imperative
programming I knew to map, filter, zip, fold and so on was going to be
important, which helped a lot. I had a good time taking things that
way, and I certainly think it should be a key point near the beginning
of any functional programming tutorial. Higher order functions, and
higher-order list processing functions in particular, are the control
structures of functional programming. They stick everything else
together. They are every bit as important as loops are to the
imperative programmer. They can also be more natural ways of thinking
about how things fit together than the imperative approach offers. My
friend, who'd had a bit of C++ and a bit of Java, (and had pretty much
hated it), preferred the Haskell approach. He gave me the example that
"map wash dishes" is a whole lot closer to what you're thinking when
washing dishes than numbering the dishes and incrementing a counter,
washing dish n at each step.

This approach to functional programming is especially important in a
lazy language, since it works so well. Lists are, in a sense, loops
which haven't yet happened, and much of programming is done by
transforming them. Due to laziness, those elements not needed won't be
computed, which is a similar capability as that of being able to break
out of a loop early. This inversion allows you to essentially extend
the code which would be in the "loop body" after the fact (that is,
without modifying the existing code), which is not something you could
do in a strict imperative language unless you'd specifically provided
for passing in a continuation in the loop, or were modelling lazy
lists somehow.

Eventually, you come to mostly forget about loops and just think in
terms of the lists themselves, but it's a very useful alternate view
to have handy.

Of course, lists aren't the only data structure just as loops aren't
the only kind of recursion. Laziness basically makes data structures
into tools giving you the ability to "reify" recursion such that only
those steps which end up needed later on are actually carried out.

 - Cale