Wed Feb 20 15:12:22 CET 2013

Love the Lambda

( From email correspondence. )

Teaching this stuff is not easy.  I applaud the brave ones that
attempt it.

I remember struggling very hard to understand the one-argument
function thing when I was learning OCaml (similar to F#). It's hard to
track back what actually changed in my understanding, but it has
something to do with changing "basic substrate" in how I think about

My understanding at this point is that *pure* functional programming
is fundamentally different from imperative programming.  I find the
"you already know X" approach in a lot of teaching to be a bit
misleading.  The problem is in the reliance on weird ways of combining
higher order functions.  Because lambda in essence is actually quite
simple once it becomes natural, all the difficulty is in building
these intricate combination patterns out of different types of
functions. I've been discussing with Antti a bit that "lambda is
low-level".  It is somewhat of a machine language in pure FP in that
it is the only thing that can be used to build any kind of program
structure.  Anything else builds on top of it.

For me it took several attempts spread over about 2 years before the

   a -> b -> c

thing started to make sense.  Then another 2 years to stop being
afraid of higher order functions (functions taking function as input)
and type constructors entering the picture, e.g.

   map :: ( a -> b ) -> ( List a -> List b )

What made me understand this, is to write programs, get deeply
confused and suddenly end up with a new way of looking at things.

I remember that starting with Scheme, I found "map" to be such a
revelation.  One way of looking at it is that everything else is sort
of a generalization of "map".

I'm thinking that teaching the use of and then the implementation of
map might be a sort of optimal point in teaching functional
programming.  Nobody cares about dorky factorials, but lists are
intuitively obvious.  Discussing map ties into functions, recursive
data structures, anonymous functions (lambda), higher order functions
and recursion.

At this point I think that pure FP

1. is really not rocket science, the underlying ideas are fairly
   simple, but

2. is *very* different from thinking sequentially and it takes some
   getting used to.

The big change is to wrap your head around thinking in data-flow and
"composable things" instead of state and sequential manipulation of

Basically, I think that there is really no shortcut in learning this,
but it is definitely learnable if you have a basic understanding of
programming. Pure FP is a new "computer architecture" that requires a
different way of thinking. But there are ways to make the transition
from imperative to pure FP a bit less painful.  My journey was

  C -> Perl -> Python -> Scheme -> OCaml -> Haskell

Each transition required a little shift in thinking.  There are
probably other ways tailored to one's specific experience.

Love the lambda ;)