What is the definition/scope of the term "catamorphism"? 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? What about the universal arrows in the free algebra construction? Are those `catamorphisms' or not? If not, is there a name for those arrows? and furthermore: 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. -- Frank Atanassow, Information & Computing Sciences, Utrecht University Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands Tel +31 (030) 253-3261 Fax +31 (030) 251-379 24-Aug-2001 12:14:45 -0300,2712;000000000000-00000018
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
participants (2)
-
Frank Atanassow -
Jeremy Gibbons