Newbie qustion about monads

[Derek Elkins]

On Thu, 02 Oct 2003 12:59:25 +0200
Juanma Barranquero <jmbarranquero at laley.wke.es> wrote:

> On Thu, 02 Oct 2003 11:22:13 +0200
> "Marcin 'Qrczak' Kowalczyk" <qrczak at knm.org.pl> 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.