From: Joe English <jenglish@flightlab.com> Date: Sat, 10 Mar 2001 09:34:28 -0800
The relevant category for Haskell is the one in which objects are types and arrows are functions. The identity arrow for object 't' is 'id' instantiated at type 'id :: t -> t', and composition of arrows is function composition.
Single-argument type constructors like '[]', Maybe, etc., map types to types (objects to objects). If equipped with a suitable function 'fmap :: (a -> b) -> (T a -> T b)' (i.e., taking arrows to arrows), they form a categorical functor (specifically, an endofunctor), and can be made instances of the Haskell Functor class.
Polymorphic functions are natural transformations: a function 'f :: forall a. F a -> G a' gives, for each object (type) 't' an arrow from 'F t' to 'G t'.
One of the definitions of a monad is: a functor M equipped with two natural transformations: eta : Id -> M and mu : MM -> M (obeying certain laws). Translating this into Haskell, this is a type constructor M along with polymorphic functions 'return :: forall a. a -> M a' and 'join :: forall a. M (M a) -> M a' (again obeying certain laws).
However, in some expositions of category theory, the usefulness of monads is justified because they 'belong' to a certain adjunction. In Haskell you can't express the adjunction, only the monad, which may take a little getting used to. But how about the related concept of an M-algebra? That is, a type T and a function 'xi :: M T -> T' so that these laws hold: xi . eta === id xi . (fmap xi) === xi . mu As it is, the List monad expresses the idea of the free monoid over a set. A List-algebra is of course a general monoid: e :: T e = xi [] (#) :: T -> T -> T (#) = \x y.xi [x y] (And 'M a' is an M-algebra for any a, using xi = join). And what you do every time you write 'foldl 0 +' in a program is to give the xi of the additive monoid structure on the Num types. Would it be useful to have functions that were polymorphic over List-algebras? (Not that I have any idea how that might be possible to express in Haskell). Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)