Monad problems: finding an m-zero

[samppi]

I'm writing a maybe/state monad using clojure.contrib.monads. I've
gotten by fine with using just (state-t maybe-m), but now I need
different behavior:
I need a monad that behaves precisely like (state-t maybe-m), except
that when a monadic value mv is called on a state s and fails, (mv s)
returns [::failure s] *instead of nil* (as maybe-m normally does).
This is the difference.

Now I'm basically done, except I can't figure out a value of m-zero
that fulfills the required axioms:
- (m-bind m-zero f) produces m-zero
- (m-bind mv (fn [x] m-zero)) produces m-zero

This is what I have so far:

(defmonad parser-m
"The monad that FnParse uses."
[m-zero (fn [state] [::failure state])
m-result (fn m-result-parser [product]
(fn [state] [product state]))
m-bind (fn m-bind-parser [rule product-fn]
(fn [state]
(let [result (rule state)]
(if (failure? result)
result
(let [[product new-state] result]
((product-fn product) new-state))))))
m-plus (fn m-plus-parser [& rules]
(fn [state]
(or (first (drop-while failure? (map #(% state)
rules)))
(m-zero state))))])

The first axiom is fulfilled:
user=> (def a (m-bind m-zero (constantly [5 [2 3]])))
#'user/a
user=> (a [0 1])
[:user/failure [0 1]]
user=> (m-zero [0 1])
[:user/failure [0 1]]

But the second is not:
user=> (def b (m-bind (constantly [:x [1 2]]) m-zero))
#'user/b
user=> (b [0 1])

And no matter what I do, I can't fulfill that second axiom. Has anyone
created this type of monad before? It seems like it should be a common
pattern: exactly like (state-t maybe-m), only failures are vector
pairs too.

[jim]

Samppi,

Here's a parser-m monad I did.

(defmonad parser-m
[m-result (fn [x]
(fn [strn]
(list x strn)))

m-bind (fn [parser func]
(fn [strn]
(let [result (parser strn)]
(when (not= nil result)
((func (first result)) (second
result))))))

m-zero (fn [strn]
nil)

m-plus (fn [& parsers]
(fn [strn]
(first
(drop-while nil?
(map #(% strn)
parsers)))))])

I explain it in:

http://intensivesystems.net/tutorials/monads_101.html

What kind of parsing are you doing?

Jim

[samppi]

Yes, your monad was the first monad that I was talking about—in fact,
I followed your tutorial when I was learning about monads, and I used
your examples to create an entire parsing library. I believe that it's
essentially equivalent to (state-t maybe-m), except that you use list
pairs instead of vector pairs. (Great job on the tutorial, by the way.
It taught me everything I knew about monads.)

In that old monad above, a monadic value's success is represented by a
vector (or a list in your example) failure result is entirely
represented by a nil. I need to change this so that failure results
are represented by regular vectors with a special first value while
preserving state—i.e., [::failure state-at-time-of-failure].

So in my new monad, for instance, the "any-char" function monadic-
value from your tutorial would instead by represented by:
(defn any-char [strn]
(if (= "" strn)
[::failure strn]
(list (first strn) (. strn (substring 1)))))

The code I posted in my original post works, except for m-zero. I
cannot figure out the proper value of m-zero so that it fulfills the
required axioms of m-zero. In the original parsing monad, it was easy
to figure out, because it's just any function that always returns nil.
But now, monadic values' failure results, like successful results, are
just vector/list pairs too.

I'll repost my code formatted for Google Group's proportional font,
with the definition of failure? included:

(defn failure? [result]
(= ::failure (get result 0)))

(defmonad parser-m
"The monad that FnParse uses."
[m-zero (fn [state] [::failure state])
m-result (fn m-result-parser [product]
(fn [state] [product state]))
m-bind (fn m-bind-parser [rule product-fn]
(fn [state]
(let [result (rule state)]
(if (failure? result)
result
(let [[product new-state] result]
((product-fn product) new-state))))))
m-plus (fn m-plus-parser [& rules]
(fn [state]
(or (first (drop-while failure?
(map #(% state) rules)))
(m-zero state))))])

My tests show me that everything works instead of m-zero, which
doesn't fulfill its axioms. This makes using :when clauses in domacro
work incorrectly for reasons I can't explain. What is this monad's
proper value of m-zero?

[jim]

Glad you found that tutorial useful. I had to run this morning, so I
couldn't really reply. I'll try to read your post more closely
tomorrow and see if I can offer any useful insight.

Jim

[samppi]

Thanks for the help.

After working it out, I just figured out that the reason why the
second axiom isn't fulfilled by the m-zero above is this part in m-
bind:
((product-fn product) new-state))))))

product-fn, which in the second axiom's case is (fn [x] m-zero), gets
called and becomes m-zero, which is in turn called on new-state, not
the old state.

I cannot figure out at all, though, what m-zero *is* valid under both
axioms. Now I don't see how it's simply possible at all—are there
monads for which there is no value of m-zero, and is this one of them?

[jim]

Samppi,

Good work on figuring that out. It's by working through those kinds of
problems that you really learn about monads. It is indeed the case
that not all monads have m-zero and m-plus defined for them. The state-
m monad is one of those. Not only that, but if you take a look at the
state-t monad transformer, you'll see m-zero defined like this:

m-zero (with-monad m
(if (= ::undefined m-zero)
::undefined
(fn [s]
m-zero)))

Notice that when you combine the state-m monad with another monad
using state-t, an m-zero for the resulting monad is only defined if
the original monad had an m-zero. Also notice that when an m-zero is
defined for the original monad, the new m-zero is a function that
accepts a state and returns the original m-zero without regard to the
state that was passed in. And that's where your original monad ran
into problems, you tried to make the new m-zero's return value
dependent on the state that was passed in.

Furthermore, it's hard to see it, but :when clauses in domonad require
that m-zero exists, and obeys the monad laws for zero and plus. So if
you're m-zero is incorrect, :when clauses won't work either.

At this point, you need to drop back and understand exactly what
you're trying to accomplish and make sure you really understand monads
as fully as possible. I just spent almost 2 weeks working on my own
monad for writing web applications. I finally gave up and sat down to
really learn how the continuation monad works. After that, I
discovered I could use it instead of writing my own and it turned out
to be very easy. Very often, you can come up with something that
almost works and think that it just needs one more tweak to get it
right. That's what happened to me and I wasted a lot of effort before
I finally tossed it out and really focused on understanding.

If you'd like to post details of what you're doing, I'd guess some
folks would lend some assistance.

Jim

[samppi]

Yes, I see. I'm going to guess that the parser-m that I give above has
no possible m-zero, so I think I'll have to rethink how I'm going to
approach this problem. I probably am going to just define failure in
another way. (The reason why I can't use nil is because I need to
store metadata on the object representing failure. I'm sure I'll
figure something out.) Thanks for your help.

[John Harrop]

Is there an explanation of monads out there that doesn't require the reader to know Haskell to understand it? One that's generic to any FP-capable language?

[Martin DeMello]

Most of them use the concrete syntax of *some* language. But this is a
good non-haskell one:

http://www.ccs.neu.edu/home/dherman/research/tutorials/monads-for-schemers.txt

martin

[John Harrop]

Thanks. 

[jim]

I wrote one specifically for monads in Clojure.

http://intensivesystems.net/tutorials/monads_101.html

There's also a second part.

Also, Konrad Hinson wrote one:

http://onclojure.com/2009/03/06/a-monad-tutorial-for-clojure-programmers-part-1

it's in 4 parts, I believe.

[Konrad Hinsen]

On 22 Nov 2009, at 22:06, samppi wrote:

> Yes, I see. I'm going to guess that the parser-m that I give above has
> no possible m-zero, so I think I'll have to rethink how I'm going to
> approach this problem. I probably am going to just define failure in
> another way. (The reason why I can't use nil is because I need to
> store metadata on the object representing failure. I'm sure I'll
> figure something out.) Thanks for your help.

Using another value than nil (e.g. a keyword) is doable:

(state-t (maybe-t identity-m ::failure))

instead of

(state-t maybe-m)

However, it seems to me (after a quick look at your initial message)
that you want m-zero to be a pair containing a keyword plus a state
value. That is not possible because m-zero has to be a constant. You
can't pack additional information on m-zero. Using metadata on m-zero
looks risky as well (but I didn't think it through to the end) because
metadata is easily lost in operations that don't expect it to be there.

Konrad.

[Konrad Hinsen]

Nothing I know of; you need some syntax if only for the examples.
Moreover, there are some fundamental differences to implementing
monads in static and dynamically typed languages.

There are two monad tutorials for Clojure programmers:

["http://onclojure.com/2009/03/05/a-monad-tutorial-for-clojure-programmers-part-1/
" "Monad tutorial part 1"]
["http://onclojure.com/2009/03/06/a-monad-tutorial-for-clojure-programmers-part-2/
" "Monad tutorial part 2"]
["http://onclojure.com/2009/03/23/a-monad-tutorial-for-clojure-programmers-part-3/
" "Monad tutorial part 3"]
["http://onclojure.com/2009/04/24/a-monad-tutorial-for-clojure-programmers-part-4/
" "Monad tutorial part 4"]
["http://intensivesystems.net/tutorials/monads_101.html" "Monads in
Clojure part 1"]
["http://intensivesystems.net/tutorials/monads_201.html" "Monads in
Clojure part 2"]]

Konrad.

[jim]

Konrad,

Glad to see you're still around doing monads in Clojure. :)

Jim

[Konrad Hinsen]

On 21 Nov 2009, at 06:31, samppi wrote:

> And no matter what I do, I can't fulfill that second axiom. Has anyone
> created this type of monad before? It seems like it should be a common
> pattern: exactly like (state-t maybe-m), only failures are vector
> pairs too.

One problem I see in your question is the little word "too". A normal
value in the monad (state-t maybe-m) is of the form (fn [state] ...).
This is not a vector pair, it's a function.

I am not familiar enough with parsing to understand *why* you want
failures represented as vector pairs. It might help you to read the
description of Parsec, an elaborate monadic parsing library in Haskell:
http://legacy.cs.uu.nl/daan/download/papers/parsec-paper.pdf
It discusses many "real-world" issues that are usually left out of
academic papers on monadic parsing. Perhaps your problem is addressed
there as well.

Konrad.

[samppi]

The original reason is that I need to be able to transfer certain
certain metadata such as memoization tables between failure results in
m-plus. I'm writing a PEG-type parser that hopefully can support left-
recursion without any conversion to right-recursive rules. I'm using
metadata because I don't want to resort to mutable state refs; even
though it's making my code more complicated, it avoids all the
problems associated with mutable state, especially keeping track of
what changes them where and how.

Right now, I've been doing fine with returning a special "Failure"
object defined by deftype with the failed state's metadata attached to
it. Thank goodness that metadata doesn't affect equality.