Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Catamorphisme
Résumé
In , the concept of catamorphism (from the Ancient Greek: κατά "downwards" and μορφή "form, shape") denotes the unique homomorphism from an initial algebra into some other algebra.
In functional programming, 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.
Consider an initial -algebra for some endofunctor of some into itself. Here is a morphism from to . Since it is initial, we know that whenever is another -algebra, i.e. a morphism from to , there is a unique homomorphism from to . By the definition of the category of -algebra, this corresponds to a morphism from to , conventionally also denoted , such that . In the context of -algebra, the uniquely specified morphism from the initial object is denoted by and hence characterized by the following relationship:
Another notation found in the literature is . The open brackets used are known as banana brackets, after which catamorphisms are sometimes referred to as bananas, as mentioned in Erik Meijer et al. One of the first publications to introduce the notion of a catamorphism in the context of programming was the paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”, by Erik Meijer et al., which was in the context of the Squiggol formalism.
The general categorical definition was given by Grant Malcolm.
We give a series of examples, and then a more global approach to catamorphisms, in the Haskell programming language.
Iteration-step prescriptions lead to natural numbers as initial object.
Consider the functor fmaybe mapping a data type b to a data type fmaybe b, which contains a copy of each term from b as well as one additional term Nothing (in Haskell, this is what Maybe does). This can be encoded using one term and one function.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.