Darren New wrote:

> Yah. :-) I'll have to ponder this s'more.

Understanding *all* of the underlying theory takes a bit of getting used 
to. (Wasn't it some physacist who said "you never truly understand new 
theories, you just get used to them"?) However, *using* it is pretty simple.

   do
     foo
     bar
     baz

It does those things in the order given. If you assign a result to a 
variable, that result stays the same thereafter. And you can do

   do
     foo
     let x = print "hello"
     bar
     x

which will print "hello" immediately after performing "bar". Nothing 
hard here. ;-)

Now, the *list* monad... that's another matter! ;-) Not to mention the 
Continuation monad. Even the documentation states that "incautious use 
of this monad will result in completely unmaintainable code". But then, 
that monad is basically for implementing new flow control constructs - 
need I say more?


<long theoretic lecture on monads>

Consider the Maybe monad. It's useful for functions that might fail. For 
example,

   solve :: Double -> Double -> Maybe Double
   solve a b = if a == 0 then Nothing else Just ((0 - b)/a)

Now, what if you wanted to perform *several* operations in sequence, 
each of which might fail? This is what the monadic structure of Maybe 
implements:

   foo j k = do
     x <- solve j k
     z <- lookup x table
     ...etc...

This is equivilent to

   foo j k =
     solve j k >>= \x -> lookup x table >>= ...

So you see that ">>=" takes a Maybe and a function that returns a Maybe, 
and... well, let me just write the code, it's faster:

   (Just x)  >>= f = f x
   (Nothing) >>= f = Nothing

So when you do "solve j k >>= f", if solve returns Nothing, just skip f 
completely and return Nothing directly. Otherwise, take whatever data 
came from solve, fish it out of the Maybe value, and feed it to f.

In other words, we can now have a chain of actions where a single 
failure triggers an escape from the whole sequence - but doesn't clutter 
up the logic of the program on paper.

Now we can do exactly the same thing with lists. If you think about it, 
a Maybe stores either 0 or 1 results. Well, a list can store 0 or 1 or 2 
or 3 or...

   xs >>= f = concat (map f xs)

As should be clear, if xs is the empty list, f is never run at all, and 
you just get an empty list as the result. This is like the Maybe case. 
Assuming xs is a nonempty list, run f for every element in xs and merge 
the results.

It gets slightly confusing when you start using do-notation, but it's 
quite powerful:

   factors k = do
     x <- [1..10]
     y <- [1..10]
     if x * y == k then [(x,y)] else []

This is a very stupid algorithm for finding all factors of k, but it 
illustrates how you can use the monadic structure of lists. Saying "x <- 
xs" basically means "x takes on all values in xs". Having two such lines 
causes the second one to cycle faster than the first one, yielding a 
Cartesian product.

Now notice that

   do
     x <- xs
     y <- ys
     f x y

is rather like the list comprehension syntax

   [ f x y | x <- xs, y <- ys ]

In fact, not "rather like", but "mathematically equivilent". Apparently 
in older versions of Haskell, comprehensions were permitted for 
*arbitrary monads*! But it was eventually decided that this is just "too 
insane" and so they removed it. Heh!

Notice that if you write

   factors k = do
     x <- [1..]
     y <- [1..]
     if x * y == k then [(x,y)] else []

you get an infinite loop. It tries all possibilities for y before moving 
on to the next possibility for x. To overcome this, you need a custom 
monad. My book at home shows you how to implement a "diagonal list" 
monad. It looks just like a list, but the [very complicated] monadic 
bind tackles combinations in diagonal order. [(1,1), (2,1), (1,2), 
(3,1), (2,2), (1,3), (4,1), (3,2), (2,3), etc.] The bind function given 
is possibly the most terrifying snippet of Haskell I have ever seen in 
my life...

</long theoretic lecture on monads>



PS. If you've got a moment, there's a Tcl implementation of my logic 
solver over in the povray.off-topic.haskell. I'd be interested to know 
if you can make it any less... butt-ugly, for want of a better word!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message