# newbie

**Lars Henrik Mathiesen
**
thorinn@diku.dk

*10 Mar 2001 20:35:44 -0000*

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