https://github.com/bwo/monads.git
git clone 'https://github.com/bwo/monads.git'
(ql:quickload :bwo.monads)
Yet another clojure library for monads, focussing on expressivity and correctness.
For Leiningen:
[bwo/monads "0.2.2"]
The idioms and terminology for this library are unabashedly
Haskellderived: there is a special syntax for monad computations,
mdo
, which is similar to Haskell's donotation, and the names (and
selection) of monads which have implementations provided out of the
box are influenced by the mtl.
All monad implementations interoperate with
clojure.algo.generic.functor
.
Internals rewritten to be faster and more flexible.
Automatic lifting in monad transformers
Applicative functors introduced; all monads support its interface.
Combined reader/writer/state monad implementation
There are some code examples, and some benchmarks, on the wiki; the examples show building up a simple expression evaluator.
Monadic computations are built up using return
and >>=
. For
instance, one could define liftm2
(which enables the application
of a function to monadic values) as follows:
(defn liftm2
"Take a function a > b > c and two values m a and m b, and return
m c."
[f m1 m2]
(>>= m1 (fn [v1] (>>= m2 (fn [v2] (return (f v1 v2)))))))
Since writing functions this way is cumbersome, a macro is provided that mimics Haskell's donotation:
(defn liftm2
"Take a function a > b > c and two values m a and m b, and return
m c."
[f m1 m2]
(mdo v1 < m1
v2 < m2
(return (f v1 v2))))
(The actual implementation of liftm2
in monads.util
is slightly
different again, due to being curried.)
However, with only return
and >>=
, we can't do anything that we
couldn't do with ordinary functions. There are also several protocols
that specific monads can implement, which bring with them specific
operations allowing more interesting things. Monad transformers can be
used to conveniently add capabilities together.
Implementations are provided for several monads:
Monad Transfomer provided? Example use case Protocols supported Specific operations 
——————————————————————
reader yes readonly access to global environment monadreader ask
, local

state yes simulate mutable state monadstate getstate
, putstate
, modify

writer yes log messages during a computation monadwriter tell
, pass
, listen
, listens
, censor

maybe yes computations may fail monadfail, monadplus fail
, mzero
, mplus

error yes computations that may fail, error handling and recovery monadfail, monadplus, monaderror fail
, mzero
, mplus
, throwerror
, catcherror

list no computations that may produce multiple results monadfail, monadplus fail
, mzero
, mplus

cont yes arbitrary manipulation of control, emulate CPS transform (none—not yet abstracted out) callcc
, shift
, reset

rws yes inline combination of reader, writer, and state monadstate, monadwriter, monadreader union of reader, state, writer 
identity yes trivial monad (none) None 
The specific operations are documented in
monads.core
,
or for the continuation operations, in
monads.cont
.
The protocols are defined in monads.types
and the functions to take
advantage of them are defined in monads.core
(with the exception of
shift
and reset
, which are defined in monads.cont
).
The “base” monads are named by suffixing m
to the names in the
table above (e.g. statem
, contm
). If there is a transformer
version of a monad, it is a function named by suffixing t
instead
of m
. The monad and transformer implementations are found in
namespaces given by the names in the table, so, e.g., statem
and
statet
are defined in monads.state
. Each such namespace also
defines vars named m
and t
as shortcuts, so you can refer to
state/m
instead of stuttering out state/statem
.
Giving the transformer function a monad as an argument returns a new
monad. The resulting “monad transformer stack” implements the
MonadTrans protocol and supports two additional operation, lift
and
inner
. inner
returns the monad that was originally passed in as an
argument; lift
can be used to run operations specific to a base
monad in the stack. In general, explicit lifting is not necessary with
the monads and transformers defined in this library, as the
transformers will automatically support the operations their arguments
do. Explicit lifting is only necessary for disambiguation if more than
one monad supports the same operation:
monads.core> (require '[monads.state :as st] '[monads.error :as e] '[monads.maybe :as m])
nil
;; the next two lines are equivalent, because `statet` will autolift `fail`
monads.core> (st/runstatet (st/t e/m) (lift (fail "oops")) :initialstate)
#<Either [:left oops]>
monads.core> (st/runstatet (st/t e/m) (fail "oops") :initialstate)
#<Either [:left oops]>
;; and the next two lines are also equivalent, because the autolifting goes down one level in the stack
monads.core> (st/runstatet (st/t (e/t m/m)) (fail "oops") :initialstate)
#<Just #<Either [:left oops]>>
monads.core> (st/runstatet (st/t (e/t m/m)) (lift (fail "oops")) :initialstate)
#<Just #<Either [:left oops]>>
;; so if we explicitly want to use `maybem`'s fail, we need to lift down from the bottom.
monads.core> (st/runstatet (st/t (e/t m/m)) (lift (lift (fail "oops"))) :initialstate)
nil
In general, monadic computations are run using runmonad
, which
takes two arguments: a monad and a monadic computation. However, as
the above example, using runstatet
, suggests, there are helper
functions for some specific monads (any of those that require extra
initial data):
Monad Run function Extra arguments 
——————————————————
state{m,t}
monads.state/runstate{,t}
Initial state 
reader{m,t}
monads.reader/runreader{,t}
Starting environment 
cont{m,t}
monads.reader/runcont{,t
} None* 
rws{m,t}
monads.rws/runrws{,t}
Initial state and starting argument 
(* In principle the extra argument should be the final continuation,
but this is actually chosen by the implementation to be return
for
contt
and identity
for contm
.)
runstate
, runreader
, runcont
, and runrws
do not need the
monad passed as their first argument, since it is assumed that the
computation should be run in the state
, reader
, cont
, or rws
monads, respectively.
The function liftm
, which lifts a function defined over types a >
b
to one defined over types m a > m b
for any monad m, is provided
in monads.core; importing this file also makes all monads correctly
treat the fmap
defined in algo.generic correctly.
A (not very systematic) selection of monad functions is provided in
monads.util
:
(sequencem ms)
: transform a sequence of monadic actions into a
monadic action yielding a sequence. (That is, go from [m a]
to
m [a]
.)
(mwhen p m)
: execute monadic computation m
if p
is truthy.
(guard p)
: exit from the computation if p
is falsy (requires
mzero
).
(liftm2 f [m [m2]])
: as liftm
but for binary functions.
There are also liftm3
through liftm8
. All the liftmn
functions are fully curried and can take at any stage anywhere
from one to the remaining number of arguments, e.g. ((liftm3 +
a b) c)
, (((liftm3 +) a) b c)
, etc. In the unlikely event
that a lifting function of yet greater arity is needed, the
defliftmn
macro can be used to create one. defliftmns
can
be used to create a range of such functions.
(liftm* f [& args])
: as liftm
but for arbitrary arities. (N.B.
this is implemented using sequencem and each appears to behave
unexpectedly in the context of the continuation monad's shift
and
reset
, but those should probably be considered experimental for
the time being).
ap
: lifts function application, but only for curried functions:
clojure
(runmonad maybem (ap (ap (return (curryfn [a b] (+ a b))) (return 1)) (return 2)))
#<Just 3>
liftm*
is likelier to be useful, unless you happen to have a lot
of curried functions lying around.
 (foldm f init xs)
: apply a reduction within a monad. NB: the
arguments here are as in Haskell's foldM
, and not as in
algo.monads
' mreduce
! foldm
expects f
to have type a >
b > m a
, init
to have type a
, and xs
to have type [b]
,
whereas mreduce
expects f
to have type a > b > a
, init
to have type a
, and xs
to have type [m b]
.
 (msum [...])
“adds” the elements of its argument list with mplus
.
Further such functions are easily defined. This, for instance, is the
definition of guard
:
(defn guard [p]
(if p
(return nil)
mzero))
These are just ordinary Clojure functions that need not know anything about the context in which they will eventually be used.
While it is perfectly possible to write monadic computations as chains
of >>=
and anonymous functions, this quickly becomes tedious; a
macro, mdo
, is provided to make things simpler. As noted above, the
syntax is very much derived from Haskell.
There are three types of elements of an mdo
form:
binding elements, which have the form destructure < expression
;
plain elements, which are just expressions (except that no such
expression can consist solely of the symbol <
or the symbol
let
);
let elements, which have the form let destructure = expression
(or let destructure1 = expression1, destructure2 = expression2,
...
. The commas here are just for presentation; since the reader
gobbles them up, they aren't (and can't be) necessary to the
syntax)
let elements may also be written with a more conventional binding
vector: let [destructure expression ...]
.
The final element of an mdo
form must be a plain element.
In the above destructure
can be any valid Clojure binding form. The
expression on the lefthand side of a binding element, and the
expression in a plain element, should have a monadic value; these are
unwrapped and bound to the binding form on the righthand side of the
binding element, if there is one. Bindings established with let
forms are, by contrast, pure (or at least treated as pure). Both forms
of bindings are visible in all following statements (if not shadowed,
of course).
So the following, for instance, is a not very interesting computation in the state monad:
(mdo {:keys [x y]} < getstate
let [z (+ (* x x) (* y y))]
(modify #(assoc % :z z))
(return z)
It does what you would expect:
> (def m (mdo {:keys [x y]} < getstate
let z = (+ (* x x) (* y y))
(modify #(assoc % :z z))
(return z)))
> (runstate m {:x 1 :y 3})
#<Pair [10 {:z 10, :y 3, :x 1}]>
> (runstatet (statet monads.maybe/maybem) m {:x 1 :y 3})
#<Just #<Pair [10 {:z 10, :y 3, :x 1}]>>
And expands into uses of >>=
and anonymous functions:
(>>=
getstate
(fn [{:keys (x y)}]
(let [z (+ (* x x) (* y y))]
(>>= (modify #(assoc % :z z)) (fn [G__6125] (return z))))))
In fact, the “let” form is not really necessary; we could have omitted it and simply written this:
(mdo {:keys [x y]} < getstate
(let [z (+ (* x x) (* y y))]
(mdo (modify #(assoc % :z z))
(return z))))
And only suffered a little indentation. Similarly, there is no need
for special syntax for if
or when
(and none is provided); just as
we can write this code:
monads.list> (def pythags (mdo a < (range 1 200)
b < (range (inc a) 200)
let a2+b2 = (+ (* a a) (* b b))
c < (range 1 200)
(monads.util/guard (== (* c c) a2+b2))
(return (list a b c))))
#'monads.list/pythags
monads.list> (take 3 (runmonad listm pythags))
((3 4 5) (5 12 13) (6 8 10))
We could have taken advantage of the fact that the return is the only statement following the guard:
monads.list> (def pythags (mdo a < (range 1 200)
b < (range (inc a) 200)
let a2+b2 = (+ (* a a) (* b b))
c < (range 1 200)
(if (== (* c c) a2+b2)
(return (list a b c))
mzero)
monads.applicative
defines a simple applicative functor interface,
and gives default implementations for it to all monads, as well as for
sequences, nil, the Just
and Either
types defined in
monads.types
, and Const
and Id
functors also defined in
monads.applicative
.
The applicative interface consists of pure
, which is analogous to
return
for monads, and effectful function application, <*>
. Since
we don't assume that all arguments will be supplied immediately,
however, the function argument to <*>
must be curried, so that
arguments can be fed in one by one. A convenience function cpure
is
supplied that takes an arity and a function and returns a curried
function with the given arity wrapped in the Pure constructor:
monads.applicative> (require '[monads.types :as t])
nil
monads.applicative> (<*> (cpure 3 +) (t/just 3) (t/just 1) (t/just 2))
#<Just 6>
monads.applicative> (<*> (cpure 3 +) (t/just 3) t/nothing (t/just 2))
nil
monads.applicative> (<*> (<*> (cpure 3 +) (t/just 3)) (t/just 1) (t/just 2))
#<Just 6>
General utilities for currying functions can be found in
monads.util
: the macros curryfn
and defcurryfn
define curried
functions, and the macro curry
and function ecurry
both take an
arity and a function and create a curried function with the given
arity. curry
falls back to ecurry
if the arity is not statically
known; if it is known, curry
is significantly faster:
monads.util> (time (dotimes [_ 10000] ((((ecurry 3 +) 1) 2) 3)))
"Elapsed time: 30.518729 msecs"
nil
monads.util> (time (dotimes [_ 10000] ((((curry 3 +) 1) 2) 3)))
"Elapsed time: 7.261895 msecs"
nil
Despite the inconvenience of manual currying, applicative functors are still useful; as an example, monads.examples.applicativefold
contains an implementation of the core of a streaming fold abstraction (though for complex computations something like babbage might be better).
Monads are implemented with a protocol defining a binary mreturn
and
trinary bind
operations; the additional parameter over return
and
>>=
is for the carrier of the protocol. There are monad
and
defmonad
macros which delegate to reify
; the followuing
definitions of the identity monad are equivalent:
(defmonad identitym
(mreturn [me x] x)
(bind [me m f] (runmonad me (f m))))
(require '[monads.types :as types])
(def identitym
(reify types/Monad
(mreturn [me x] x)
(bind [me m f] (runmonad me (f m)))))
However, monad
and defmonad
allow one to conditionally support
other protocols as well, which is useful for defining monad
transformers that support a protocol if the transformed, inner monad
does.
Since the macros know that they are defining a monad, nothing special
needs to be done to ensure that mreturn
and bind
find their homes
in the right protocol; other protocols need to be given explicitly
using reify
like syntax. For example, the readert
transformer
function looks like this:
(defn readert [inner]
(monad
(mreturn [me v] (constantly (types/mreturn inner v)))
(bind [me m f] (fn [e]
(runmdo inner
a < (m e)
(runreadert me (f a) e))))
types/MonadTrans
(inner [me] inner)
(lift [me c] (fn [e] (runmonad inner c)))
types/MonadReader
(ask [me] (fn [e] (types/mreturn inner e)))
(local [me f m] (fn [e] (runreadert me m (f e))))
(when (types/monadfail? inner)
types/MonadFail
(fail [me msg] (fn [e] (types/fail inner msg))))
(when (types/monadplus? inner)
types/MonadPlus
(mzero [me] (constantly (types/mzero inner)))
(mplus [me lr] (fn [e]
(types/mplus inner
(lazypair (runreadert me (first lr) e)
(runreadert me (second lr) e))))))))
Note the conditional support for MonadFail
and MonadPlus
.
The use of the “bare” monads (maybem, errorm, etc.) is vulnerable to
stackblowing on deeply nested computations, e.g. (msum (repeat 4000
mzero))
. This danger can be mostly obviated by using the
transformer version of the monad with contm as the base monad:
monads.maybe> (require '[monads.util :as u] '[monads.cont :as c])
nil
monads.maybe> (runmonad maybem (u/msum (repeat 4000 mzero)))
; Evaluation aborted.
monads.maybe> (c/runcont (runmonad (maybet c/m) (u/msum (repeat 4000 mzero))))
nil
On a less trivial computation:
monads.examples.treenumber> (require '[monads.cont :as c])
nil
monads.examples.treenumber> (def x (numtree (longtree 10000)))
StackOverflowError monads.core/fn1769 (core.clj:63)
monads.examples.treenumber> (def x (c/runcont (s/runstatet (s/t c/m) (numbertree (longtree 10000)) {})))
#'monads.examples.treenumber/x
monads.examples.treenumber> (count (second x)) ;; check that we've actually got the right # of entries
10000
However, this doesn't get around the entire problem: msum is written to associate to the right. A leftassociative version would still blow the stack:
monads.maybe> (c/runcont (runmonad (maybet c/m) (reduce mplus mzero (repeat 4000 mzero))))
; Evaluation aborted.
The same thing happens with nested binds on the left:
monads.maybe> (monads.cont/runcont (runmonad (t monads.cont/m)
(reduce (fn [acc _] (>>= acc (fn [x] (return (inc x)))))
(return 0)
(range 10000))))
StackOverflowError monads.types.Bind (types.clj:33)
However, since we have a programmatically manipulable representation of the computation, this difficulty can be worked around:
monads.maybe> (monads.cont/runcont (runmonad (t monads.cont/m)
(monads.cont/reorganize (reduce (fn [acc _] (>>= acc (fn [x] (return (inc x)))))
(return 0)
(range 10000)))))
#<Just 10000>
monads.maybe> (monads.cont/runcont (runmonad (t monads.cont/m)
(monads.cont/reorganize (reduce #(mplus %1 %2)
mzero
(repeat 10000 mzero)))))
nil
Monadic computations are required to ensure the behavioral identity of
(>>= (>>= m f) g)
and (>>= m (fn [x] (>>= (f x) g)))
, so the
reorganize
function can convert leftbiased computations with the
former shape to rightbiased computations with the latter. Since
mplus
is similarly required to be associative, it does the same for
leftbiased mplus
applications, rewriting (mplus (mplus a b) c)
to
(mplus a (mplus b c))
.
Note that this reorganization at present doesn't descend into the
monadic arguments of e.g. local
, and (obviously) the contents of
closures in the second argument of >>=
are opaque to it. If the
rewriting were baked into mplus
and >>=
, this would not be an
issue, but I'm hesitant to carry the rewriting out if it's not asked
for.
Copyright © 2014 Ben Wolfson
Distributed under the Eclipse Public License, the same as Clojure.