MorphismA term related to category theory describing a map between two objects in an abstract category. Morphisms can have varying properties, but can generally be considered mappings, analogous to functions.
There are several types of basic morphisms, all relative to the categories that they belong to:
- A general morphism.
- A morphism f such that fu = fv implies u = v. In the category of sets, where morphisms are functions, it is equivalent to injectivity of the function.
- A morphism f such that uf = vf implies u = v. In the category of sets this is equivalent to surjectivity of the function.
- This is a morphism which can be inverted. In the category of sets this is equivalent to say that the morphism is both a mono- and epi- morphism, i.e. a bijection, but while any isomorphism is always both mono and epi, not in every category the vice versa is true. Alternately, it can be described as a map which preserves sets and relations among elements.
- A homomorphism from one object to itself.
- An isomorphism from one object to itself.
These are very abstract. They relate to TUNES in that these are concepts which describe high-level logical properties of functions. These logical properties can be used to form and use strategies about how to evaluate programs without involving the specification of the program. Although, some meta-level annotations on the program may involve strategies.
From some of the papers in our category theory 101 course, some more specific morphism types (of the category of algebras or co-algebras) that would be more relevant to programming are:
- A "downwards" morphism: one that maps from some structured object to some object which is the subject of the structure. Any function which accumulates some value from a structure (such as fold or reduce) fits this concept. By being abstract, this can also cover program structures.
- The dual to a catamorphism, this type of morphism constructs a structure.
- Basically, the composition of a cata- and ana- morphism, which transforms between data structures in some way.
- A variation on anamorphisms describing functions with co-inductively-defined target types (streams, graphs, etc.).
The meaning of the fact that these are part of algebraic categories means that they apply to programs which can be algebraically-described. See the papers of Martin Erwig, particularly Categorial Programming with Abstract Data Types, which describes abstract data types as bi-algebras (This is hardly easy to read. Please add some easier explanation here).