Hobby-hacking Eric

2009-02-21

implementing join in terms of (>>=)

One of the things I got out of the Typeclassopedia is a somewhat more mature understand of monads (at last!). As a bonus side-effect it has also given me a slightly better understanding of myself. Specifically, I learned I often have trouble learning things because I suffer from a sort of "failure to unify". I thought I might make a note of it for the benefit of anybody else who is interested in how they learn... or not, as the case may be.

So,
  • we have (>>=) :: m a -> (a -> m b) -> m b
  • we want join :: m (m x) -> m x
My mind drew a complete blank. So I went with something "direct" via do notation:
join mmx =
do mx <- mmx
x <- mx
return x
Those last two lines are redundant:
join mmx =
do mx <- mmx
mx

Hang on, Eric, surely you don't need the crutch of do notation...
join mmx = mmx >>= (\mx -> mx)
That's just id:
join mmx = mmx >>= id

But wait! Surely that can't be right! Doesn't (>>=) require something of type a -> m b? And isn't id giving me m x -> m x? I stared at that for a while, almost panicking. What did I do wrong? And then it clicked. Of course, the a in a -> m b could stand in for any type, including m x. Just because it doesn't have a little m in it, doesn't mean that it's constrained not to have one.

A simpler version of this kind of error, although one that didn't get me this time: just because we have a and b doesn't mean we actually have to have two different types. They can, but don't need to. And that, is my "failure to unify", inventing completely illusory constraints and not seeing through them.

And so join is just (>>= id). It took a little struggle, but it was well worth it!

(PS, in my original attempt, I used the more conventional m (m a) when thinking of the types instead of what I reported here, m (m x). The reason I reported the later is because I didn't want to confuse the discussion with another stumbling block I have, which is a "failure to rename", i.e. forgetting that two things called a in different contexts are actually two separate things. It's like speaking a foreign language. Just because you are aware that you have to do something, doesn't mean you will always do it automatically. Anyway, the "failure to rename" may very likely have conspired with the "failure to unify" in making me confused for a while)


2 comments:

Unknown said...

I know what you mean by these "failures." I get them all the time. :-/

Anonymous said...

extend = (=<<) is more natural than (>>=) IMO. Just look at that gorgeous type signature:

extend :: (a -> m b) -> m a -> m b

And then we have the beautiful definitions:

join = extend id
extend f = join . extend f

By the way, I have those little mismatches a lot. Before implementing a tough algorithm, I will spend an hour or two just being a computer and doing it on paper. It's really annoying when those cognitive errors come up in that context, especially if I don't catch them for a while. (but it certainly makes me remember, and take care when implementing that point)