categories: Re: "catamorphism"

[Jeremy Gibbons <Jeremy.Gibbons@comlab.ox.ac.uk>]

> In the calculational school of programming, I think people agree that:
> 
>   For every F-algebra A, the unique F-homomorphism from an initial F-algebra to
>   A is a catamorphism.
> 
> but:
> 
>   Is the converse true also, or is `catamorphism' more general: "a
>   catamorphism is the unique arrow from an initial _object_ (in any category,
>   not just categories of algebras)." I think the answer to that question is
>   no, but is there a snappy name for such arrows?

Erik Meijer coined the name "catamorphism". According to
him, the name was chosen because the Greek prefix "cata"
means "downwards"; a catamorphism destructs a data structure
like a list. (For example, "sum" destructs a list of
numbers, yielding a number.)

So I would agree with you. For example, in Set, the unique
arrow from the initial object (the empty set) to any other
object does not "destruct", so should not be called a
catamorphism.

>   In the case of initial F-algebras, for F an endofunctor on category C, is the
>   catamorphism the arrow in the category of F-algebras, or the corresponding
>   one in C? In other words, is `catamorphism' a property of the arrow or the
>   arrow + the category? If you compare with `monomorphism', since we speak of
>   being `monic _in_ C', I presume the latter, and thus only one arrow would be
>   `catamorphic', but which? Judging from the literature, I am inclined to
>   say that the arrow in C is the catamorphism, but I would like a second
>   opinion.

It is the arrow in C. In programming terms, it is the
program itself (eg "sum") that destructs; the arrow in the
category of F-algebras is merely an artifact of the
categorical way of modelling such programs.

IMHO.

Jeremy

-- 
Jeremy.Gibbons@comlab.ox.ac.uk
  Oxford University Computing Laboratory,    TEL: +44 1865 283508
  Wolfson Building, Parks Road,              FAX: +44 1865 273839
  Oxford OX1 3QD, UK.  
  URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html