Mon Aug 29 23:34:20 CEST 2011

The Essence of Functional Programming

I'm reading [1] again.  What I see now when seeing the monad types is
that essentially the beef is really hidden behind the type M.

  return :: a -> M b
    bind :: M a -> (a -> M b) -> M b

I wrote about this before in different words[2], but the real click
for me is that a Monad is 1. completely general wrt. the a and b in
the types above, and 2. completely abstract in that all its magic is
hidden behind the type M and the bind, return operations.

So if it's completely abstract, how can you create a function of type
a -> M b in the first place?  To be useful, every monad needs to
export some function to create values wrapped in M on top of the
standard composition interface made up by bind and return.

M a is always a value.  However, it doesn't have to be a naked value
of type a.  It can be the output of a function as in the Reader monad
:: e -> a, or the input of a function as in the Cont (CPS) monad :: (a
-> r) -> r.

Wadler mentions[1] that the basic idea when converting a pure function
into a monadic one is to convert a function of type a -> b to one of
type a -> M b.  The return and bind operations can then compose these
functions, or more intuitively[3], it can compose Kleisli arrows (a ->
M b) -> (b -> M c) -> (a -> M c).

What I've always found strange is that the do notation has such a
peculiar form if you think of it.  It has little to do with Kleisli
composition where arrows are not nested.  A do block has a single
return type M r, but several nested functions with input a1, a2, a3,
... one for each arrow.

The thing is that do notation is to let (applicative style) what
Kleisli composition is to function composition (point-free style).
It's not so much that do is strange, it's that nested let is strange!
In some sense a point-free approach is more natural compared to
creating a context of many visible variables to allow random access.

[1] http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps.gz
[2] entry://20110723-141330
[3] http://blog.sigfpe.com/2006/06/monads-kleisli-arrows-comonads-and.html