[Haskell-cafe] Levels of recursion

J. Garrett Morris trevion at gmail.com
Fri Feb 2 16:00:30 EST 2007

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

The first time I really thought about this much was after reading
Meijer, Fokkinga and Patterson's "Functional Programming with Bananas,
Lenses and Barbed Wire," which makes the comparison between arbitrary
recursion and goto early on, and develops four replacement operators
(cata-, ana-, hylo-, and paramorphisms).  At the time, I was involved
in teaching an introduction FP class in which we frequently discovered
that students would latch onto primitive recursion early in the course
and never stop using it, even as their functions became more
convoluted and using maps and filters correspondingly easier.  My
natural thought was to wonder if the beginning of the course could be
rewritten without primitive recursion, only introducing it later after
the students were already comfortable with the higher-order

Sadly, that never went anywhere.  I'd be interested in hearing if
anybody else got farther in attempting that teaching technique.


It is myself I have never met, whose face is pasted on the underside of my mind.

More information about the Haskell-Cafe mailing list