|
 |
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
|
|
