Lably
Skip to content

Catamorphism

Homomorphism from an initial algebra into another algebra

  • 19 min read
  • 3 chapters

Related on Lably

Through Category (mathematics) and Natural number

Lab · Class 2Data Handling (Pictographs)Lab · Class 4–6Graphs DataLab · Class 9–11Graph PlotterLab · Class 6–12Data Visualization Lab

Catamorphisms provide generalizations of folds of lists to arbitrary algebraic data types, which can be described as initial algebras. The dual concept is that of anamorphism that generalize unfolds. A hylomorphism is the composition of an anamorphism followed by a catamorphism.

Definition

Consider an initial F-algebra (A,in) for some endofunctor F of some category into itself. Here in is a morphism from FA to A. Since it is initial, we know that whenever (X,f) is another F-algebra, i.e. a morphism f from FX to X, there is a unique homomorphism h from (A,in) to (X,f). By the definition of the category of F-algebra, this h corresponds to a morphism from A to X, conventionally also denoted h, such that h∘in=f∘Fh. In the context of F-algebra, the uniquely specified morphism from the initial object is denoted by cataf and hence characterized by the following relationship:

  • h=cataf
  • h∘in=f∘Fh

Sign in to keep reading

2 more chapters are free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard