[Haskell-beginners] Re: Yet another monad tutorial.

[Benjamin L.Russell]

On Mon, 5 Jan 2009 09:08:37 -0200, "Rafael Gustavo da Cunha Pereira
Pinto" <RafaelGCPP.Linux at gmail.com> wrote:

>Hello everyone
>
>
>I am a very eclectic person when it comes to computer languages, and I found
>this monad tutorial for OCaml programmers:
>
>http://enfranchisedmind.com/blog/2007/08/06/a-monad-tutorial-for-ocaml/
>
>I found it to be very interesting, since it shows those "warm, fuzzy things"
>implemented in another functional language with very clear explanations of
>what he is doing in each step.
>
>Best regards, and a happy 2k9 for you all!
>
>Rafael

>From the aforementioned monad tutorial for O'Caml programmers:

>A ‘newbie’, in Haskell, is someone who hasn’t yet implemented a compiler. They’ve only written a monad tutorial.
>    -Pseudonymn

Fascinating.

>Forget category theory. Forget space suits and free will and all the other bad analogies floating around about Monads. 
>Monads are first and foremost a design pattern, as in the Gang of Four “Design Patterns” book. 

An interesting perspective.  The focus on design patterns brings to
mind the book How to Design Programs (see http://www.htdp.org/), by
Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, and the
recent dialect of Typed Scheme (see
http://www.ccs.neu.edu/home/samth/typed-scheme/), as well as the
language Qi (see http://www.lambdassociates.org/whatsnew.htm).

There is a somewhat similar tutorial on monads using Qi (see
"Programming Kung Fu Qi: Monads in Qi" at
http://programmingkungfuqi.blogspot.com/2007/02/monads-in-qi.html).

For reference, I shall use the Haskell-based monad tutorial "All About
Monads" (see http://www.haskell.org/all_about_monads/html/index.html)
as a base for one of the Haskell versions of the examples.  Most of my
descriptions of the Haskell version will be borrowed from the
descriptions contained in the section there entitled "Meet the Monads"
(see http://www.haskell.org/all_about_monads/html/meet.html).

Let's compare the Haskell version with the O'Caml version and a
hypothetical pure Scheme version:

Haskell version of monad rules (borrowed from the Qi-based tutorial
(not the Haskell one)):
>class Monad m where
>   return :: a -> m a
>   (>>=)  :: m a -> (a -> m b) -> m b

O'Caml version of monad rules (borrowed from the O'Caml-based
tutorial):
>module type MonadRequirements = sig
>    type ‘a t
>    val bind : ‘a t -> (’a -> ‘b t) -> ‘b t
>    val return : ‘a -> ‘a t
>end;;

Hypothetical pure Scheme version of monad rules (borrowed from the
Qi-based tutorial):
>   (pipe (lift x) f)   = (f x)
>   (pipe m lift)       = m
>   (pipe (pipe m f) g) = (pipe m (lambda (x) (pipe (f x) g))

The Haskell version is the most concise.  The "return" and "(>>=)"
("bind") operations in Haskell correspond to the "return" and "bind"
operations in the O'Caml version, and to the "lift" and "pipe"
operations in the hypothetical pure Scheme version.

In the Haskell version, "m" is the type constructor, "return" is an
operation that creates a value of the monad type "m a," while "(>>=)"
(a.k.a. "bind") is an operation that combines a value of that type "m
a" with a computation that produces values of that type to produce a
new computation for values of that type "(a -> m b) -> m b."

Superficially, so far, the three versions seem fairly equivalent to
me.

Now for examples of list monads:

Haskell version (adapted from combining the Haskell-based and the
Qi-based tutorials):
>instance Monad [ ] where
>   l >>= f = concatMap f l
>   []     >>= f = []
>   return x     = [x]

Your O'Caml version (borrowed from the O'Caml-based tutorial):
>module ListMonad = struct
>    type ‘a t = ‘a list;;
>
>    let bind lst f = List.concat (List.map f lst);;
>
>    let return x = [ x ];;
>end;;

Qi version (borrowed from the Qi-based tutorial):
>(define bind
>   [] _ -> []
>   [X | Xs] F -> (append (F X) (bind Xs F)))
>
>(define return
>   X -> [X]  )

Here we start to see some differences.

In the Haskell version, "return" simply creates a singleton list
("[x]"), while "(>>=)" (i.e., "bind") either returns a blank list "[]"
in the case of a blank list, or otherwise creates a new list
containing the results of applying the function to all of the values
in the original list "concatMap f l."

In the O'Caml version, notice the "List.concat" operation.  After the
List.map operation, we are left with not a "‘a list", but instead
with a "‘a list list", so this is necessary to obtain the correct
type "‘a list."  Otherwise, the reasoning is similar.

In the Qi version, we have split the monad into two functions:  "bind"
and "return."  Splitting a large function into a smaller functions is
typical Scheme style.  Here, "return" simply pattern-matches an
element into a list containing that element, while "bind" either
pattern-matches an empty list "[]" following by anything "_" to an
empty list "[]," or pattern-matches a list consisting of a car and a
cdr "[X | Xs]," followed by a function "F," to "F" applied to "X,"
which is "(F X)," appended to a binding of the cdr of the list "Xs" to
the function "F."

It seems that studying the Qi version may shed some insight into the
Haskell version by approaching it from a different perspective.  This
may also be true of the O'Caml version, but personally, I think that
the splitting of the monad into separate functions for "bind" and
"return" in the Qi version helps to differentiate it from the other
two versions, and hence offers additional insight into the nature of
the monad.

It may also be said that the use of both "List.map" and "List.concat"
in the O'Caml version offers similar insight.

Now for a pet peeve that I have with one of the examples in the O'Caml
monad tutorial:

>module SerialMonad = struct
>    type ‘a t = unit -> ‘a;;
>    let serial_mutex = Mutex.create ();;
>    let return x = (fun () -> x);;
>    let bind m g = (fun () -> (g (m ())) ());;
>    let access m =
>        Mutex.lock serial_mutex;
>        try
>            let r = m () in
>            Mutex.unlock serial_mutex;
>            r
>        with
>        | e ->
>            begin
>                Mutex.unlock serial_mutex;
>                raise e
>            end
>end;;
>
>This monad is basically identical to the previous FunMonad with the addition of the access function- which executes the 
>process while holding the serial_mutex lock, which is always unlocked when the process completes (even if the process 
>throws an exception). This forces all processes executing within a SerialMonad to be executed sequentially and serially 
>(thus the name).

While a clear example, one problem that I have with this approach is
that the emphasis on forcing "all processes executing within a
SerialMonad to be executed sequentially and serially" reminds me of
the Imperative Way.  This brings to mind a posting by Paul Hudak on
Haskell-Cafe, entitled "a regressive view of support for imperative
programming in Haskell," dated "Wed Aug 8 14:20:39 EDT 2007" (see
http://www.haskell.org/pipermail/haskell-cafe/2007-August/030178.html),
in which he writes as follows:

>In my opinion one of the key principles in the design of Haskell has 
>been the insistence on purity.  It is arguably what led the Haskell 
>designers to "discover" the monadic solution to IO, and is more
>generally what inspired many researchers to "discover" purely functional 
>solutions to many seemingly imperative problems.  With references and 
>mutable data structures and IO and who-knows-what-else to support the 
>Imperative Way, this discovery process becomes stunted.
>
>Well, you could argue, monad syntax is what really made Haskell become 
>more accepted by the masses, and you may be right (although perhaps 
>Simon's extraordinary performance at OSCOM is more of what we need).  On 
>the other hand, if we give imperative programmers the tools to do all 
>the things they are used to doing in C++, then we will be depriving them 
>of the joys of programming in the Functional Way.  How many times have 
>we seen responses to newbie posts along the lines of, "That's how you'd 
>do it in C++, but in Haskell here's a better way...".

Although I greatly applaud alternative perspectives in learning
Haskell, I am somewhat suspicious of the emphasis on a
quasi-imperative approach.  One of the factors that initially
attracted me to Haskell in the first place was the emphasis on a
functional style.  In particular, purely functional code has a number
of advantages, including easier reasoning about program behavior,
easier formulation of proofs of correctness, and referential
transparency. Together with referential transparency comes
applicativity of formal methods of program analysis.  All this is lost
once the Functional Way is replaced by the Imperative Way.

Here, the Qi-based monad tutorial seems to focus more on examples that
use the functional approach, but perhaps this is just my opinion.

Comparative programming languages can be a very interesting topic.  If
anybody knows of any alternative monad tutorials in other functional
programming languages that could help to shed light on monads, please
feel free to mention them in this thread.

-- Benjamin L. Russell
-- 
Benjamin L. Russell  /   DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile:  +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto." 
-- Matsuo Basho^ 
-- 
Benjamin L. Russell  /   DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile:  +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto." 
-- Matsuo Basho^