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.

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 type Tree a. treeDepth et sumTree 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)

1. ↑ (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