http://clojure.googlegroups.com/web/monads.clj
In my original implementation, I had used keywords for the monad
operations. These keywords were replaced by their definitions inside a
given monad using a recursive symbol replacement in the form to be
evaluated. This approach has a major problem: it doesn't combine correctly
with macros. If a macro expands into a form containing monad operation
keywords, they are not replaced at all, because my symbol replacement code
sees only the original form.
The new implementation uses plain functions for the monad operations. The
with-monad form
expands into a straightforward let form that binds the operations to their
names. Generic monad operations such as lift are implemented as functions
that take the four basic monad definitions as additional parameters. These
functions are wrapped by macros that add these parameters to the argument
list. In the new implementation, all form manipulation is done by macros,
and there is much less of it: it no longer has a fundamental role, but
just provides nicer syntax.
To pursue my original idea of a replacement-based implementation, one
would need something like Common Lisp's symbol-macrolet, which is however
not trivial to implement. It requires either an integration with the
compiler's macro expansion mechanism, or a separate implementation of full
macro expansion, including subforms, of an arbitrary form.
With the new monad implementation, client modules can:
- define new monads (monad and defmonad)
- define new generic monad operations (defmonadfn)
- execute code using a monad (with-monad)
- define functions that internally use a specific monad (define the
function inside a with-monad block)
- use monad comprehension syntax (domonad)
Some minor changes:
- All monad operations have names starting with m-.
- There is a single m-lift that takes its arity as an argument.
- m-plus takes an arbitrary number of arguments and respects lazy evaluation.
Konrad.
thanks for your comments!
> First, the function 'group' that you define seems to be the same as
> Clojure's 'partition' function.
Indeed. I have spent some time checking if something like this exists
already, but I didn't consider "partition" as a name!
> Second, when I tried to load monads, I get the following error.
>
> java.lang.ExceptionInInitializerError (monads.clj:
> 165)
> Caused by: java.lang.ExceptionInInitializerError
> Caused by: java.lang.RuntimeException:
> java.lang.ClassNotFoundException: user$m_PLUS_m_seq_PLUS_m__252
> at clojure.lang.RT.readString(RT.java:1163)
> at user$m_PLUS_m_map_PLUS_m__272.<clinit>(monads.clj:165)
> ... 26 more
> Caused by: java.lang.ClassNotFoundException: user
> $m_PLUS_m_seq_PLUS_m__252
The definition of m-map makes use of m-seq, which is a macro that
expands into a call to the function m+m-seq+m. It seems that this
function doesn't exist on your system. It should have been created by
the (defmonadfn m-seq...) just before.
On my system this works fine, but since I use a pretty old Clojure
version (the 20080916 release), it is possible that something
important has changed since. Unfortunately I can't easily test with
more recent SVN versions as I live behind a firewall that doesn't let
the SVN protocol pass.
Konrad.
> I would make some minor changes in two places. I would write with-
> monad as:
Obviously this is a better version.
> And I would write m-lift as
I like that one as well.
I have uploaded a new version that integrates your improvements.
Another one is that the monad operations are now named functions (a
feature I discovered by accident), which helps in debugging.
> I've also modified my parser combinator monad and uploaded a new
> version at:
>
> http://groups.google.com/group/clojure/web/monad-parser%20%282%29.clj
That looks like a good opportunity to look at monadic parsers...
Konrad.
> Also, I came across set-state and fetch-state being implemented in
> terms of update-state.
Indeed, those are the implementations I had in my first monad
implementation. I replaced them by manually inlining update-state
when I wanted to get rid of monad-operation substitution at monad
creation time. In the current version, these clearer implementations
can be used again.
Konrad.
you were quicker than me in implementing monad transformers! What I
had in mind is exactly what you did: a monad transformer would be
implemented as a function taking a monad as an argument. That's in
fact why I defined the monad macro in addition to defmonad.
> I did some more work from the paper the parser combinator is based
> on. From that I built what I think is a state monad transformer:
That's exactly what it is. In fact, it looks like a translation of
the Haskell implementation.
There is one aspect of your implementation that I don't like: it
exposes the internal representation of monads as maps. This can be
avoided by using "with-monad m" in the definition of the monad
operations:
(defn stateT [m]
(monad [m-result (with-monad m
(fn m-result-state-t [v]
(fn [s] (m-result (list v s)))))
m-bind (with-monad m
(fn m-bind-state-t [stm f]
(fn [s]
(m-bind (stm s)
(fn [[v ss]]
((f v) ss))))))
m-zero (with-monad m
(when m-zero
(fn [s] m-zero)))
m-plus (with-monad m
(when m-plus
(fn m-plus-state-t [& stms]
(fn [s] (apply m-plus (map #(% s) stms))))))
]))
It should also be possible to write m-bind as a monad comprehension
in the inner monad:
m-bind (with-monad m
(fn m-bind-state-t [stm f]
(fn [s]
(domonad
[[v ss] (stm s)]
((f v) ss)))))
This looks clearer to me, but I didn't test if it actually works.
> I also rewrote the maybe monad as:
...
Why did you do this? Did you just want a more concise implementation,
or is there a difference in behaviour? As far as I can see, your
version of m-bind does exactly the same as mine for all input values
that can occur in the given context. Yours would also do something
useful given a vector of more than one value, but that should never
happen in the maybe monad.
Konrad.