Catamorphisme

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 type Tree a. treeDepth et sumTree sont appelés algèbres.

Catamorphisme dans la théorie des catégories

Notes et références

  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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Catamorphisme de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Anamorphisme — Traduction à relire Anamorphism → Anamorphisme …   Wikipédia en Français

  • Paramorphisme — Traduction à relire Paramorphism → Paramorphis …   Wikipédia en Français

  • Charity (langage) — Traduction à relire Charity (programming language) → …   Wikipédia en Français

  • anamorphisme — ⇒ANAMORPHISME, subst. masc. Procédé utilisant l anamorphose à des fins artistiques, pour en tirer des effets insolites : • La mode des jeux de perspective a fort baissé au XIXe siècle, mais elle a été remise en honneur, curieusement, par le… …   Encyclopédie Universelle

  • catamorfism — CATAMORFÍSM, catamorfisme, s.n. (geol.) Totalitatea proceselor care se produc în partea superioară a scoarţei terestre. – Din engl. catamorphisme. Trimis de valeriu, 03.03.2003. Sursa: DEX 98  catamorfísm s. n. Trimis de siveco, 10.08.2004.… …   Dicționar Român

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”