- Catamorphisme
-
Dans la théorie des catégories, le concept de catamorphisme (du Grec: κατα- = vers le bas; morphisme = forme) dénote l'unique homomorphisme pour une algèbre initiale. Le concept a été appliqué dans la programmation fonctionnelle.
Le concept dual est celui d'anamorphisme.
Sommaire
Le catamorphisme dans la programmation fonctionnelle
En programmation fonctionnelle, un catamorphisme est une généralisation de la fonction fold sur les listes au cadre de types algébriques de données quelconques pouvant être décrit comme des algèbres initiales.
Une des premières publications visant introduire la notion d'anamorphisme dans le contexte de la programmation fut l'œuvre Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire[1], par Erik Meijer, et qui fut dans le contexte du langage de programmation Squiggol.
Les catamorphismes sont une forme duales des anamorphismes, eux-mêmes généralisation des opérations de type unfold.
Exemple
L'exemple suivant en Haskell définit un catamorphisme sur une structure d'arbre (de type
Tree a
) :data Tree a = Leaf a | Branch (Tree a) (Tree a) type TreeAlgebra a r = (a -> r, r -> r -> r) foldTree :: TreeAlgebra a r -> Tree a -> r foldTree (f, g) (Leaf x) = f x foldTree (f, g) (Branch l r) = g (foldTree (f, g) l) (foldTree (f, g) r) treeDepth :: TreeAlgebra a Integer treeDepth = (const 1, \l r -> 1 + max l r) sumTree :: (Num a) => TreeAlgebra a a sumTree = (id, (+))
Ici,
foldTree (f, g)
est un catamorphisme sur le typeTree a
.treeDepth
etsumTree
sont appelés algèbres.Catamorphisme dans la théorie des catégories
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Catamorphism » (voir la liste des auteurs)
- (en) Erik Meijer, Maarten Fokkinga et Ross Paterson, « Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire », dans CiteSeerX, 1991 [texte intégral]
Voir aussi
Articles connexes
- Anamorphisme
- Hylomorphisme
- Paramorphisme
- Apomorphisme
Wikimedia Foundation. 2010.