[Haskell-cafe] Article review: Category Theory

Yitzchak Gale gale at sefer.org
Fri Jan 19 07:01:28 EST 2007

I wrote:
>> OK, so then how about
> > f .! g = ((.) $! f) $! g

Ulf Norell wrote:
> That should probably do the trick.

OK, thanks! Time to re-write the "Note"
paragraph yet again. Here goes a first
shot at it:

: <code>id . f = f . id = f</code>

'''''Note:''''' It turns out that the usual identity function <code>id</code>
and composition function <code>(.)</code> in Haskell are actually not
exactly what we need for the '''Hask''' category.

The function <code>id</code> in Haskell is ''polymorphic'' - it can
take many different types for its domain and range, or, in
category-speak, can have many different source and target objects. But
morphisms in category theory are by definition ''monomorphic'' - each
morphism has one specific source object and one specific target
object. A polymorphic Haskell function can be made monomorphic by
specifying its type (''instantiating'' with a monomorphic type), so it
would be more precise if we said that the identity morphism from
'''Hask''' on a type <code>A</code> is <code>(id :: A -> A)</code>.
With this in mind, the above law would be rewritten as:

: <code>(id :: B -> B) . f = f . (id :: A -> A)</code>

The Haskell composition function <code>(.)</code> is lazy, so the
required identity
<code>id . f = f</code> is not true when we take <code>f = undefined</code>:
we have <code>(id . undefined) `seq` "foo" = "foo"</code>, but
<code>undefined `seq` "foo"</code> is equivalent to <code>undefined</code>.

To fix this problem, we can define a strict composition function:

: <code>f .! g = ((.) $! f) $! g

Now the above law looks like this:

: <code>(id :: B -> B) .! f = f .! (id :: A -> A)</code>

In this form, the law is correct, and ''Hask'' is a category.
However, for simplicity, we will ignore these distinctions
when the meaning is clear.


More information about the Haskell-Cafe mailing list