OK, so "magma" consists of a set S and a binary operator #. The # 
operator takes any two elements of S (including the possibility of two 
copies of the same element), and yields a new element of S (possibly the 
same one you started with).

   ∀ x, y ∈ S, x # y ∈ S.

The only "rules" as such are picky, hair-splitting ones. Stuff like "x # 
y" must have a single, definite value for all possible inputs. (If, for 
example, # stands for division, then if y=0, there is no defined result. 
If we're working with integers only, 2/3 isn't an integer. And so on.)

A magma isn't especially interesting by itself. However, if we add the 
rule that # must be /associative/, then we got a "semigroup".

   ∀ x, y, z ∈ S, (x # y) # z = x # (y # z).

Already this begins to have interesting mathematical properties. But if 
we add a special /identity element/, we get a "monoid".

   ∃ i ∈ S: ∀ x ∈ S, i # x = x # i = x.

So what are we really saying? We're saying that a monoid is a set of 
things that have a procedure for combining them, and that there has to 
be a special one where combining it does nothing.

There are many possible examples of this. For example, if S is a set of 
numbers and # denotes addition, then 0 is our identity element. (Every 
child knows that x + 0 = x.) Less obviously, if # denotes 
multiplication, our identity element is 1. (Since 1 * x = x.)

But there are other examples too. If S is the set of all possible text 
strings, and # denotes concatenation, then the identity element is the 
empty string. (Appending or prepending an empty string does nothing.) If 
S is the set of all 1-argument functions [with the same return type as 
their argument type], and # denotes function composition, then the 
identity FUNCTION is the identity ELEMENT. (Bet you can't work out how 
/that/ naming scheme came about. :-P )

If you now take your monoid and give every element a corresponding 
/inverse element/, then you have a "group".

   ∀ x ∈ S, ∃ y ∈ S: x # y = y # x = i.

For example, in the monoid of numbers where # is addition, the inverse 
of (say) 5 would be -5. And hence, numbers and addition actually form a 
/group/, not just a monoid.

Considering strings, however, there is no string that you can append to 
something which "undoes" the act of appending an earlier string. So 
strings with concatenation form a monoid, but not a group.



All of this is fascinating, of course, but not directly related to MONADS.

If somebody asks "what is a monad?", the stereotypical response is

   "A monad is just a monoid in the category of endofunctors - what's 
the problem?"

The problem, obviously, is that if you don't know category theory, this 
makes not one shred of sense.

A less abstract way to think about it is this: If you have a value like 
x, you can put that inside a "box", which I will denote as [x]. Any 
value can be put in a box; in particular, you can put a /box/ in a box, 
for example [[x]].

Every /monad/ is also a /functor/. This merely means that there's a 
function (usually called "map"):

   map :: (x -> y) -> ([x] -> [y])

In other words, it takes a function that works an x-values, and turns it 
into a function that works on boxes containing x-values. (And instead of 
returning y-values, it now returns boxes containing y-values.) In 
summary, it "lifts" a function from working on values, to working on 
values in boxes.

The alternative way to think about map is

   map :: (x -> y) -> [x] -> [y]

In other words, given a function from x to y, and an x in a box, I will 
give you a y in a box.

Either way, there's a way to apply an ordinary function to values in 
boxes. Given that, there are two equivalent ways to define a monad. They 
both involve a function called "return":

   return :: x -> [x]

Return just takes a value and puts it in a box. "Inject" or "insert" 
might be a better name, but for some reason we're stuck with "return". 
Ho hum.

The other function is either "join" or "bind". One can be defined from 
the other - although this is highly non-obvious.

Join is the easy one to understand:

   join :: [[x]] -> [x]

It takes a box within a box, and gives you just a box. It removes one 
level of boxiness. That's pretty easy to comprehend.

Bind, on the other hand, has the hoopy type signature

   bind :: [x] -> (x -> [y]) -> [y]

In other words, given...
- An x in a box.
- A function that wants an x and gives you a y in a box
...I can give you a y in a box.

Notice how the x arrives IN A BOX, but the function expects a value NOT 
IN A BOX. So bind has to take a value /out/ of a box. Right? Right??

Actually... no. You can implement it just using join:

   bind box_x function = join (map function box_x)

Applying the function to the x inside the [x] yields a result of type 
[[y]]. Applying join to that turns it from [[y]] into [y] - the required 
result type.

Less obvious still is that join can be defined using bind:

   join bbx = bind bbx id

Here "id" is the identity function - i.e., a function that takes one 
argument, and just returns it unchanged. Recall that bind takes a value 
out of a box and passes it to a function. Well in this case, the value 
in the box is another box, so if we just /return/ that, we'll have only 
one level of boxing.

Usually it's bind that you actually want to /use/, and hence it's more 
efficient to define join in terms of bind, rather than the other way 
around. (Haskell actually lets you define return and bind without 
bothering with map at all. Map can be defined in terms of bind and 
return, after all: map f = bind (return . f).)



The really hoopy thing, of course, is that this "box" I keep talking 
about usually isn't just a simple box. (If it were, that would give you 
the identity monad, which is the most boring monad there is.) Usually 
it's something more interesting.

For example, if [x] represents a /list/ of x-values (as it does in 
Haskell, by the way), then [[x]] is a list of lists, and join is just 
flattening a list of lists into a single list. Alternatively, bind is 
mapping your function over every element of the list, and then 
flattening the resulting list of lists into a single list. (You will 
sometimes hear Haskell's bind operator is being "concatMap". "concat" is 
a standard library function that does what join does above; "concatMap" 
does the same as calling map and then concat.)

Sometimes, however, Haskellers do crazy things, like where your "box 
with an x in it" is actually a /function/ which takes half a dozen 
arguments and then /returns/ an x. For example, if [x] means "a function 
that takes a dictionary and then returns an x", then... Well, we end up 
with /a lot/ of different functions flying around, which can sound a bit 
confusing. But here it is:

- return(x) just generates a new function that accepts a dictionary, 
ignores it, and always returns x anyway.

- map(f,g) is easy enough. Return a function that takes a dictionary, 
calls g with that dictionary, and then applies f to the result.

- join(f) is taking a function that returns a function that returns an 
x. At this point we don't /have/ a dictionary, so we have nothing to 
actually /call/ f with as an argument. But we want to make a function 
that takes a dictionary and returns an x. So we write a function that 
takes a dictionary argument, calls f with it, and then calls the result 
of f again with the same argument.

- Given that we have join() and map(), it's clear that bind() should be 
implementable. But can we do it more directly? In fact, all bind(f,g) 
does is return a function that takes a dictionary, calls f with that 
argument, and then passes the result to g. Quite easy, really.

As a result of all this jiggery-pokery, you can write simple-looking 
code, but it invisibly has access to this dictionary that we keep 
passing around the place. For that to actually be useful, you need a way 
to /fetch/ the dictionary. You go that by writing a function like

   get_dictionary :: [dictionary]

Notice that this doesn't appear to be a /function/ at all; it takes no 
arguments, after all. But it appears to be a "dictionary in a box" - and 
as we just discussed, in this instance our "box" is really "a function 
that takes a dictionary and returns something". It should be obvious how 
you would write "a function that takes a dictionary and returns a 
dictionary".

So this complex arrangement of stuff allows every piece of code that 
runs inside this specific monad to have [read-only] access to a 
dictionary object. (Obviously it's not hard to change it to be some 
other sort of object instead.) This is the so-called "reader monad".

It's all fascinating stuff... but rather mind-bending in places. ;-)

Post a reply to this message