Haskell Slides

[Levi Pearson]

Hi all,

I cleaned up the slides a bit and added some reference URLs throughout. Many are links to research papers on the topics rather than tutorial-style material, and although the "meat" of some of them goes over my head, it's at least interesting to see a rough timeline of when many of these topics were first hashed out. Note that the boxes in the URLs should be tildes; I didn't want to dig into why they got munged like that.

http://pinealservo.com/HaskellSlides.pdf

For some book-length tutorial material, I can recommend these:

Learn You a Haskell For Great Good!  http://learnyouahaskell.com/

Real World Haskell  http://book.realworldhaskell.org/

Parallel and Concurrent Programming in Haskell  http://chimera.labs.oreilly.com/books/1230000000929

This is by no means finished or a shining example of Haskell code, but here's an IRC server I'm in the middle of writing in Haskell ( http://cgit.pinealservo.com/pipes-irc-server/).  I've tried to keep the core data types and their manipulating functions pure and non-monadic while providing a couple of non-IO monads as a convenience for grubby validation and error handling code.  The commands all transform the server state inside a STM transaction.

       --Levi

 

[Levi Pearson]

Someone asked why anyone would call the Monad method 'return' by the
name 'unit', and I just remembered. The reason is, as you might
suspect, related to abstract math stuff, so feel free to skip this
email if you don't care. :)

In abstract algebra and its even more abstract cousin category theory,
we often want to talk about mathematical objects with a certain kind
of structure. To start out concrete, think of the set of positive
integers.

One thing we can do with integers is to multiply them together. When
we do that, we get another integer. So we say that multiplication is
closed under the set of positive integers.

It so happens that you can group multiplication operations over the
set of positive integers however you like and it doesn't change the
meaning; i.e. (2 * 3) * 4 == 2 * (3 * 4). We say that multiplication
over the positive integers is associative.

There is also a special number with the property that when you
multiply by it, whether on the right or left, you get back the same
number. This happens to be the number 1 for the set of positive
integers. It doesn't matter whether you do, for example, 3 * 1 or 1 *
3; you still get 3 back. So we say that 1 is the left- and
right-identity element for multiplication over the positive integers.

We've just described an algebraic object called a Monoid, which is
some set of values equipped with an associative binary operator, which
is closed over that set, and which has a unique value that's a left
and right identity for that operator. For some reason, the canonical
binary operator is often called multiplication, and so we call the
identity element 'unit' since that's another somewhat more abstract
name for 1.

You can also form a Monoid over the set of positive integers with
addition as your binary operator, in which case the identity element
would be 0 rather than 1. And you can form a Monoid over the set of
Strings, with string concatenation being the binary operator and the
empty string being the identity element. So when we're talking about
addition-like Monoids, we sometimes call the identity element a 'null'
instead of a 'unit', although it's *still* unitary in the sense that
there's only one of them.

Another interesting Haskell Monoid is the one defined on the type
'newtype Endo = Endo { appEndo :: a -> a }`. We have `instance Monoid
(Endo a)` where our binary operation is composition of functions, i.e.
the (.) operator, and the identity element is... the identity function
id! This is handy if you have a whole bunch of `a -> a` functions that
you want to compose together, perhaps selecting them dynamically and
then composing them together to apply with a map. Just create a list
of them and mconcat the list of Endos!

Anyway, so that's where the term 'unit' comes from. So why would we
use it to describe the 'return' method of Monad? Well, Monads are
actually Monoids in the category of endofunctors on Hask (the category
of Haskell-native data types and functions), with multiplication being
composition of endofunctors and unit being the identity endofunctor.
(This is a paraphrase of a bit from MacLane's "Category Theory for the
Working Mathematician", but you may also recognize it from a bit of
humor: http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html).

If you squint really hard at the type signatures in Haskell, this
might make some kind of sense immediately. All Haskell instances of
'Functor' are in fact endofunctors on Hask, because they take types to
types and functions on the base type to functions on the new type. And
the point of Haskell's version of Monad is to "accumulate" extra
"stuff" while composing these Monadic things. And when you use
'return', you are not supplying any extra "stuff", so it shouldn't
affect the "accumulation". From the description above about Monoid, it
should be clear that although they are not *just* about accumulation,
they do capture the essence behind accumulation and other similar
things. I'm not going to attempt to write this out in Haskell, but
the multiplication here is related to the flattening operation inside
of `join`; i.e. we have 1 -> X via return and X * X -> X via the join.
This is related to the Eilenberg-Moore category associated with a
given Monad.

Monads also form a different category known as the Kleisli category,
and in Haskell we represent composition in the Kleisli category with
the `>=>` operator, which has type `(a -> m b) -> (b -> m c) -> a -> m
c`. The argument order is 'flipped' from standard function
composition order in order to relate it to the standard definition of
`>>=`, which is that way for convenience in writing things out in
de-sugared form instead of do expressions. If you look at the type
signature for return again, it should be clear how the things fit:
`return :: a -> m a'. You can fit that on either side of `>=>` and,
assuming your Monad obeys the Monad laws, you end up with:

return >=> g = g -- return is the
left-identity for >=>
g >=> return = g -- return is the
right-identity for >=>
(g >=> h) >=> k = g >=> (h >=> k) -- >=> is associative

And the definition of `>=>` is just `f >=> g = \x -> f x >>= g`, so
there's not really any extra machinery going on here. These aren't the
Monoid laws about the "composition of extra stuff", these are the
Category laws that explain the structure of a Category just like the
Monoid laws explain the structure of a Monoid. But again there's an
identity element, and there's only one of them, so `return` is a unit
in this sense too. So the Monad laws are just the Category laws in
disguise, and they assure us that we can compose Monadic expressions
as we'd like to.

So there are two different reasons we might want to call `return` by
the name `unit`, but both of them require some math that is likely to
be less than helpful to someone who's just trying to grasp the *usage*
of monads in Haskell, which is actually pretty straightforward as long
as you don't get caught up on the word 'Monad'. But `unit` does have
the advantage that it doesn't get wrongly associated with the notion
of returning from a procedure call in an imperative language.

Personally I'd call it `pure` instead, as this captures the idea
there's no extra 'stuff' associated with the value, it's just being
lifted to the Monad in the default, straightforward way. This is
actually what the same function is called in the context of the
Applicative class, which could fill another lengthy email or a
presentation.

--Levi