Lars Henrik Mathiesen
10 Mar 2001 20:35:44 -0000
> From: Joe English <email@example.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) <firstname.lastname@example.org> (Humour NOT marked)