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 24-Aug-2001 12:14:59 -0300,12425;000000000000-00000019