Catamorphisme

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 (en), et qui fut dans le contexte du langage de programmation Squiggol (en).

Les catamorphismes sont une forme duales des anamorphismes, eux-mêmes généralisation des opérations de type unfold.

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, (+))

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Catamorphism » (voir la liste des auteurs).