So, the question remains: when the monad laws say that

(return x) >>= f == f x

what is intended in that "=="?

Observational equivalence. For monads like list and maybe, this boils down to the normal equality because the standard equality on these types is exactly observational equality. For monads like IO, you can't define an Eq instance so it comes down to what can the user of the program observe. They can observe the order you create files or write to files. They can even observe the order you open files. They can't observe 'internal' actions that don't have side effects and don't depend on the IO environment so 'return' should not be observable. In particular, they can't see any of the returns in this sequence: do return 1 return 2 return 3 print 42 Which is a good thing since the monad law you cite requires this to be equal to print 42 For monads like parser monads, there is usually a notion of encapsulation. That is, you're supposed to be able to observe the results of running the parser and you may also be able to observe how much input was examined but you probably can't directly observe the internal state of the parser. In that case, we'd consider two states to be equivalent if they lead to the same results being returned and the same input being examined. Since parsers are state transformers, we'd say that two parsers are equivalent if they preserve and reflect equivalence of states. (There's a little circularity there and I'm ignoring the exception part of parser monads but, hopefully, you get the idea.) -- Alastair Reid www.haskell-consulting.com

On Thu, 02 Oct 2003 12:59:25 +0200 Juanma Barranquero wrote:

On Thu, 02 Oct 2003 11:22:13 +0200 "Marcin 'Qrczak' Kowalczyk" wrote:

...

As you discovered, there is no meaningful count of operations. If an operation doesn't do anything, do you count it?

The Count monad with return defined as Count 0 a with >>= adding them is an instance of the Writer/Output monad. Using 1 and addition isn't. It's also a potentially useful monad. I've seen the equivalent called the Complexity monad before. Using that intuition, return a is something that has 0 complexity. What you needed to do was add primitives that have a complexity you want to measure. For example if you were considering space complexity, you might have a cons primitive defined as say, cons x xs = Count 2 (x:xs), but multiplication, say, would have zero complexity. In general you could use a HOF to add complexity annotations to functions or add a bump = Count 1 () to bump up the complexity of some computation, cons x xs = bump >> bump >> return (x:xs)

It's not about counting the operations (that's just an example), but accumulating any kind of state.

This isn't state, this is, again, a (broken) instance of the Writer/Output monad. The return should use the empty list and your >>= doesn't even make sense.

For example:

data Accum a = Ac [a] a

instance Monad Accum where return x = Ac [x] x Ac _ x >>= f = let Ac l x' = f x in Ac (l ++ [x']) x'

dupAcc x = Ac [x,x] x

m1 = (return 'a') >>= dupAcc -- Ac "aaa" 'a' m2 = dupAcc 'a' -- Ac "aa" 'a'

Which shows that your monad is broken. As Markus mentions, -you- have to make sure the monad laws hold, they don't come for free. If they don't hold, you don't have a monad.

...

but monad laws say that "return" *really* doesn't do anything

I don't see it. As I understand, the problem (if any) would be in my implementations of either >>= or f (dupAcc, in this case). I get the same values for m1 and m2 even if I define return x = Ac [] x.

As Marcin said, return doesn't do anything. In fact, I believe the monad laws together effectively state that both >>= and return are "pure" with respect to whatever computation is being modelled. So the associativity condition says that it doesn't matter which >>= is evaluated first. Another thing that should be noted, is that most monads are completely useless without "primitive" computations. I.e. using only >>= and return will get you nothing that couldn't have been done "purely". This can be seen by considering the similarity between monads and monoids. return corresponds to the neutral element of a monoid, while join m = m

...

= id is the multiplication. One example of a monoid is the natural numbers with 0 as the neutral element and + as the multiplication. If we only use 0 and + the result is rather boring, 0+0+0+0, 0+0. This is similar to only using return and >>=. If we use other elements (corresponding to primitive monadic computations) things are much more interesting, 4+90+0+2, 10+3.

So again, with Accum, you need a "primitive" computation that actually is effectful while return and >>= aren't, with the Writer monad this is tell :: [a] -> Writer() which is similar to putStr except it doesn't perform IO, it just collects up a list of "output". The Haskell wiki has implementations of various monads.

I'm not trying to create useful monads (I'm pretty sure they aren't :), but understanding the concepts. So, the question remains: when the monad laws say that

(return x) >>= f == f x

what is intended in that "=="? Eq."==" for

instance Eq MyCustomMonad where x == y = whatever...

or a more profound kind of equality?

A more profound kind, as it usually isn't possible to define a reasonable instance of Eq for monads. Anyways, these laws are the ones from the Category Theory definition of monads (slightly restructured), obviously they aren't talking about Haskell's Eq or even computable equality in general.

From your examples and interpretations, it looks like you need to become more familiar and comfortable with -using- monads before you bother trying to write one. Then once you have that down, seeing how -correct- monads work would probably be the next most helpful thing. You'll have a very hard time thinking up correct monads if you don't have any intuition about how they are supposed to be used. In any case, knowing how to write an instance of Monad is probably the least useful thing to know about them in Haskell.

On Thu, 02 Oct 2003 14:27:29 +0200 "Marcin 'Qrczak' Kowalczyk" wrote:

Accumulating state is fine. These definitions don't accumulate state: 'return' should yield a "neutral" state, and the above ">>=" ignores the state of the lhs.

You're right.

data Accum s a = Ac [s] a

instance Monad (Accum s) where return x = Ac [] x Ac s1 x >>= f = let Ac s2 y = f x in Ac (s1++s2) y

output :: a -> Accum a () output x = Ac [x] ()

Nice. Thanks! Juanma

Incidentally, it is quite common to define a Monad instance but no Eq instance. (e.g., the IO monad, most parser monads, most state transformer monads, etc.) So you should not interpret the '==' in the monad law as requiring you to define an Eq instance. If you do define an Eq instance, it ought to be reflexive, symmetric and transitive (i.e., an equivalence) if you want functions with Eq constraints to behave in a meaningful way. Also, although there's probably no necessity for your Eq instance to match your notion of equality between computations (i.e., the == used in the monad laws), I think you'll end up very confused if you define an Eq instance which doesn't match in the same way that having Eq on pairs ignore the 2nd field would confuse you. -- Alastair Reid www.haskell-consulting.com

So, the question remains: when the monad laws say that

(return x) >>= f == f x

what is intended in that "=="? Eq."==" for

instance Eq MyCustomMonad where x == y = whatever...

or a more profound kind of equality?

As Derek has pointed out, I'm yet far from reaching a point where I should worry about that :)

_If_ you understand Haskell but not monads, I think it is entirely legitimate to start with the implementation and then proceed to the uses. A bottom-up approach instead of a top-down approach. This is the approach of Will Partain's old 'country boys guide to monads' (which I can't find a copy of). He started with examples of non-monadic code where you couldn't see what was going on because of all the 'plumbing' required to make sure you had a supply of fresh names here and a current substitution there and showed how a monad could cleanup the plumbing. Of course, this only works if you've written enough of the right kind of code that the examples make sense... -- Alastair Reid www.haskell-consulting.com