A Cross-language Comparison of Monads in Haskell, O’Caml, and Qi

A few days ago, there was an interesting post by Rafael Gustavo da Cunha Pereira Pinto, dated “Mon, 5 Jan 2009 09:08:37 -0200,” on the Haskell-beginners mailing list on the Haskell programming language, referencing a monad tutorial for the O’Caml programming language that provided an alternative perspective in helping to illustrate monads in Haskell, mentioned in the thread “Yet Another Monad Tutorial.” In my response, I introduced an alternative monad tutorial for the Qi programming language, which also referenced Haskell.

Since the O’Caml monad tutorial mentioned design patterns as an alternative to category theory in forming a basis for describing monads, this reminded me of the book How to Design Programs, by Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, which led to a mention of Typed Scheme, which in turn led to a mention of Qi.  In turn, this led to a cross-language comparison of monad definitions in Haskell, O’Caml, and Qi, and their implications.

Hereinafter I have quoted parts of my response for reference (with minor edits to hyperlink various keywords, as opposed to leaving the link URL’s separate from their references):

The focus on design patterns brings to
mind the book How to Design Programs, by
Felleisen, Findler, Flatt, and Krishnamurthi, on Scheme, and the
recent dialect of Typed Scheme, as well as the
language Qi.

There is a somewhat similar tutorial on monads using Qi (see
“Programming Kung Fu Qi: Monads in Qi”).

For reference, I shall use the Haskell-based monad tutorial “All About
Monads” 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”.

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):
>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.

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]

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 “[]” followed 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”,
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.

What’s interesting about this comparative programming languages-perspective is that it seems that studying both Haskell and Qi together may actually lead to learning Haskell more quickly than learning just Haskell alone, because the cross-language perspective helps to motivate and shed light on the trickier parts of Haskell semantics.