In this post, I’ll build a monad
library for Racket, using its
generic interfaces
feature in place of Haskell’s type classes.
There have been lots of demonstrations of monads in dynamicallytyped
languages before; notably,
Oleg’s article on monads in Scheme. However, I haven’t
yet (Update: see below) seen one that smoothly
allows for returntype polymorphism.
This post introduces (1) coercions between monad representations and
(2) “undecided” quasimonadic placeholder values. Taken together,
these give a Haskelllike feel for monads in a dynamicallytyped
language.
The techniques are illustrated using Racket, but aren’t specific to
Racket.
The Challenge
How can we write monadic programs like this, where monad types are
implicit, just as they are in comparable Haskell programs?
(runio (do (mdisplay "Enter a number: ")
n < mread
alln < (return (for/list [(i n)] i))
evens < (return (do i < alln
#:guard (even? i)
(return i)))
(return evens)))
The overall computation uses do
notation at IO type, while the
evens
list uses do
notation at List type.
The problem
Simple monomorphic monads are easy. Here’s the List monad in Racket:
(define (fail) (list))
(define (return x) (list x))
(define (bind xs f) (appendmap f xs))
Let’s add some simple do
notation sugar:
(definesyntax do
(syntaxrules (<)
[(_ mexp) mexp]
[(_ var < mexp rest ...) (bind mexp (λ (var) (do rest ...)))]
[(_ mexp rest ...) (bind mexp (λ (dummy) (do rest ...)))]
[(_ #:guard exp rest ...) (if exp (do rest ...) (fail))]))
Now we can write list comprehensions. For example, let’s select the
odd numbers from a list, and multiply each by two:
>>> (do i < '(1 2 3 4 5)
#:guard (odd? i)
(return (* i 2)))
'(2 6 10)
Let’s define another monad! How about for
Racket’s lazy streams?
(define (fail) emptystream)
(define (return x) (streamcons x emptystream))
(define (bind s f) (if (streamempty? s)
emptystream
(let walk ((items (f (streamfirst s))))
(if (streamempty? items)
(bind (streamrest s) f)
(streamcons (streamfirst items)
(walk (streamrest items)))))))
This is a fine definition, as far as it goes, but we’ve just run into
the first problem:
Monads behave differently at different types
Simply defining fail
, return
and bind
as functions won’t work.
We need some kind of dynamic method dispatch. Haskell does this by
dispatching using
dictionary passing.
But there’s a deeper problem, too:
Monads don’t learn their types until it’s too late
How should we choose which dictionary to use? It’s easy with bind
,
because the specific monad being bound is always given as bind
’s
first argument. The bind
implementation can be a method on the
monad’s class.
This doesn’t work for return
or fail
. When they’re called, they
don’t know what kind of monad they should produce. That only becomes
clear later, when their results flow into a bind
.
Haskell uses the type system. We have to do it at runtime, on a
casebycase basis.
A solution
To address these problems, we explicitly represent the dictionary we
need:
(struct monadclass (failer ;; > (M a)
returner ;; a > (M a)
binder ;; (M a) (a > (M b)) > (M b)
coercer)) ;; N (M a) > (N a)
The failer
, returner
and binder
methods correspond to the monad
operations we met above, but coercer
is new. It lets us dynamically
reinterpret a monad at a different monadic type. We’ll see its use
below.
Now we can define our List monad class:
(define List
(monadclass (λ () '())
(λ (x) (list x))
(λ (xs f) (appendmap (λ (x) (coerce List (f x))) xs))
notcoercable))
The notcoercable
function is for use when it’s not possible to
reinterpret the type of a monad, which is the overwhelmingly common
case. It checks to make sure we’re already at the expected type, and
raises an exception if we’re not.
(define (notcoercable N m)
(if (eq? (monad>monadclass m) N)
m
(error 'coerce)))
We need some way of learning which dictionary to use for a given monad
instance. It’s here that Racket’s generics come in:
(definegenerics monad
(monad>monadclass monad)
#:defaults ([null? (define (monad>monadclass m) List)]
[pair? (define (monad>monadclass m) List)]))
This declares a new generic interface, gen:monad
, with a single
method, monad>monadclass
. It supplies implementations of
gen:monad
for the builtin types null?
and pair?
, in each case
returning the List
monadclass when asked.
Now we can implement bind
and coerce
, not just for a single monad, but for all
monads:
(define (bind ma a>mb)
(define binder (monadclassbinder (monad>monadclass ma)))
(binder ma a>mb))
(define (coerce N ma)
(define coercer (monadclasscoercer (monad>monadclass ma)))
(coerce N ma))
They use monad>monadclass
to find the relevant dictionary, extract
the right method from the dictionary, and delegate to it.
Note that bind
dispatches on its first argument, while coerce
dispatches on its second argument: monad instances get to decide how
they are bound and how (or if!) they are to be interpreted at other
monad types.
Next, we introduce neutral quasimonad instances for when return
and fail
don’t know which monad type to use. Because we might bind
such a quasimonad before it collapses into a particular type, we need
to define a quasimonad to represent bind
s in superposition, too.
(struct return (value)
#:methods gen:monad [(define (monad>monadclass m) Return)])
(struct fail ()
#:methods gen:monad [(define (monad>monadclass m) Fail)])
(struct suspendedbind (ma a>mb)
#:methods gen:monad [(define (monad>monadclass m) Bind)])
The Return
method dictionary looks very similar to the
implementation of the
identity monad,
with the addition of a return
struct box around the carried value:
(define Return
(monadclass (λ () (error 'fail))
(λ (x) (return x))
(λ (m f) (f (returnvalue m)))
(λ (N m) ((monadclassreturner N) (returnvalue m)))))
There are two interesting things to note here:

The bind implementation is a direct statement of one of the monad
laws,
return x >>= f ≡ f x

The coerce implementation rebuilds the
monad using the return
implementation from the target monad.
The Return
coerce implementation gives us the equivalent of
returntype polymorphism, letting us avoid sprinkling monad type
annotations throughout our code.
Fail
and Bind
are implemented similarly: ^{1}
(define Fail
(monadclass 'invalid
'invalid
(λ (ma a>mb) (suspendedbind ma a>mb))
(λ (N m) ((monadclassfailer N)))))
The coerce
method for an undetermined failure calls the new
monadclass’s failer
method to produce the correct representation
for the final monad.
(define Bind
(monadclass 'invalid
'invalid
(λ (ma a>mb) (suspendedbind ma a>mb))
(λ (N m) (bind (coerce N (suspendedbindma m))
(suspendedbinda>mb m)))))
Likewise, coerce
for a suspendedbind
rebind
s its parameters, after first coercing
them into the nowknown monad.
You might have noticed a call to coerce
in the bind
implementation
for List
above:
(λ (xs f) (appendmap (λ (x) (coerce List (f x))) xs))
This is necessary because f
might simply (return 1)
, which is one
of these neutral quasimonad instances that needs to be told what kind
of thing it should be before it can be used. On the other hand, f
might have returned (list 1)
, in which case List
’s coercer method
will notice that no conversion needs to be done.
The IO Monad
Racket is an eager, imperative language, and so doesn’t need an IO
monad the way Haskell does. But we can define one anyway, to see what
it would be like.
It’s also useful as a template for implementing unusual control
structures for monadic embedded domainspecific languages.
Values in the IO type denote sequences of delayed actions. We’ll
represent these using two structure types, one for return
and one
for bind
:
(struct ioreturn (thunk)
#:methods gen:monad [(define (monad>monadclass m) IO)])
(struct iochain (io k)
#:methods gen:monad [(define (monad>monadclass m) IO)])
(define IO
(monadclass (λ () (error 'fail))
(λ (x) (ioreturn (λ () x)))
(λ (ma a>mb) (iochain ma a>mb))
notcoercable))
Lifting Racket’s primitive input/output procedures into our IO type is
straightforward:
(define (mdisplay x) (ioreturn (λ () (display x))))
(define mnewline (ioreturn newline))
(define mread (ioreturn read))
Finally, we need a way to actually execute a builtup chain of
actions:
(define (runio io)
(match (coerce IO io)
[(ioreturn thunk) (thunk)]
[(iochain io k) (runio (k (runio io)))]))
Revisiting the Challenge Problem
We now have all the pieces we need to run the challenge program given
above.
The challenge comes from the end of Oleg’s article on
monadic programming in Scheme. His example uses many different types
of monad together, using the monomorphic technique he developed:
(IO::run
(IO::>> (putline "Enter a number: ")
(IO::>>= (readint)
(λ (n)
(IO::>>= (IO::return (for/list [(i n)] i))
(λ (alln)
(IO::>>=
(IO::return
(List:>>= alln
(λ (i)
(if (even? i)
(List::return i)
(List::fail "odd")))))
(λ (evens) (IO::return evens)))))))))
With our polymorphic monads, we are able to use the generic
do
notation macro defined above, and write instead
(runio (do (mdisplay "Enter a number: ")
n < mread
alln < (return (for/list [(i n)] i))
evens < (return (do i < alln
#:guard (even? i)
(return i)))
(return evens)))
which compares favourably to the Haskell
main = do putStr "Enter a number: "
n < getInt
allN < return [0 .. n1]
evens < return $ do i < allN
guard $ i `mod` 2 == 0
return i
return evens
Implementation
A somewhat fleshedout implementation of these ideas is available
here:

It uses
prop:procedure
,
making monadclasses directly callable and allowing (coerce List
foo)
to be written as (List foo)
.

It uses the
doubledispatch pattern
to let monad instances flexibly adapt themselves to each other in
coercions. For example, lists, streams and sets can all be
considered interconvertible.

It uses Racket’s builtin exception type to represent pending
failures instead of the simple structure sketched above. This way,
failures may carry stack traces and an informative error message.

It includes a simple State
monad, with sget
and sput
operations.
I based this work on some
experiments I ran back in 2006
in writing a monadic library for Scheme. Racket offers much better
support for objectoriented/generic programming (among many other
things!) than vanilla Scheme does, which makes for smoother
integration between my monad library and the rest of the language.
Ben Wolfson pointed me to his
monad library for clojure in a
reddit thread
about this post. It seems to be using a very similar approach, with
“neutral” carriers for monadic values that stay neutral until a later
point in the program. The main difference seems to be that with my
approach, no “run” step is needed for some monads, since monadic
values carry their bind
implementation with them. Ben’s library
supplies the bind implementation at “run” time instead.
Update, 20150127: Paul Khuong pointed me to
his Scheme monad implementation
based around
delimited continuations
in
this twitter conversation.
It doesn’t have dynamicdispatch for automatically determining the
appropriate bind
implementation, but I suspect it could be added;
perhaps in his join
operator, which makes an interesting contrast to
the technique explored in this post. The really nice thing about the
delimited continuation approach to monads is that the return
is
implicit. You never mention return
explicitly in monadic code.
That makes a big difference, because returntype polymorphism is only
needed to handle explicit returns
! By placing the return
right
next to the appropriate run
operation, the delimited continuation
technique neatly sidesteps the problem.
Conclusions
Haskell’s return
is generic: it injects a value into any monad at
all. Which specific monad is used depends on the context. This is
impossible to directly implement in general without static analysis.
Lacking such static analyses in dynamicallytyped languages, achieving
the equivalent of Haskell’s return
is challenging, even though
implementing particular monomorphic variations is straightforward.
The trick is to make return
produce a kind of superposition which
doesn’t collapse to a specific monad type until it touches a monad
that already knows what type it is.
In this post, I’ve shown how this kind of monad “coercion” works well
to give the kind of returntype polymorphism we need to make monads
feel in Racket similar to the way they do in Haskell.