newbie

[Lars Henrik Mathiesen]

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