Re: Newbie qustion about monads

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.