Anamorphisme

L'anamorphisme (du Grec: ανα- = vers le haut; morphisme = forme) est un concept de la programmation fonctionnelle fondé sur la théorie des catégories.

Sommaire

L'anamorphisme en programmation fonctionnelle

En programmation fonctionnelle, un anamorphisme est une généralisation des fonctions de type unfold permettant la création générique de liste au cadre des types de données arbitraires qui peuvent être décrites par des coalgèbres finales (ou « algèbres initiales »). Les anamorphismes, qui sont corécursifs (en) , sont la forme duale des catamorphismes récursifs, tout comme les unfolds sont une forme duale des folds.

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.

Exemples

Anamorphismes sur des listes

Un anamorphisme dans le cadre de listes est tout simplement un unfold : il produit une liste (potentiellement infinie), à partir d'une graine donnée. En Haskell, une définition d'un anamorphisme serait :

-- Signature de type de 'ana':
ana :: (b->(a,b)) -> (b->Bool)-> b -> [a]   
-- Définition de la fonction 'ana' :
ana unspool finished x = if finished x
                        then []
                        else a : ana unspool finished y
                            where (a,y) = unspool x

Cet anamorphisme générique permet de définir de nombreuses fonctions. Par exemple, on peut facilement écrire une fonction d'itération iterate2 sur une liste :

iterate2 f = ana (\a -> (a, f a)) (\_ -> False)

Anamorphismes sur d'autre type de données

On peut définir un anamorphisme sur n'importe quel type de données récursif, et pas nécessairement une liste. Par exemple, un unfold sur un arbre

data Tree a = Leaf a | Branch Tree a Tree

peut être défini par :

-- Signature de type de 'ana':
ana :: (b->Either a (b,a,b)) -> b -> Tree a
-- Définition de la fonction 'ana' :
ana unspool x = case unspool x of
                  Left a -> Leaf a
                  Right (l,x,r) -> Branch (ana unspool l) x (ana unspool r)

L'anamorphisme dans la théorie des catégories

Dans la théorie des catégories, l'anamorphisme est le concept dual du catamorphisme.

Notation

Une notation pour \mathrm{ana} \ f trouvée dans la littérature est [\!(f)\!]. Les parenthèses utilisées sont connues sous le nom de lens bracket (parenthèse « lentille ») en raison de la ressemblance avec une lentille optique, après qui les anamorphismes réfèrent parfois aux lenses (lentilles).

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 Anamorphisme de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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

  • Catamorphisme — ██████████40  …   Wikipédia en Français

  • anamorfism — anamorfísm s. n. Trimis de siveco, 10.08.2004. Sursa: Dicţionar ortografic  ANAMORFÍSM s.n. Formarea de minerale noi, de compoziţie mai complicată şi cu densitate moleculară mai mare, din altele mai simple şi cu densitate mai mică. [< fr.… …   Dicționar Român

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

  • Hans Holbein Le Jeune — Hans Holbein le jeune, (1543), portrait par Lucas Horenbout d après un dessin d auto portrait Hans Holbein le jeune est un peintre et graveur allemand, né à Augsbourg en 1497 et décédé à Londres le 29 novembre 1543 …   Wikipédia en Français

  • Hans Holbein le jeune — Hans Holbein le jeune, (1543), portrait par Lucas Horenbout d après un dessin d auto portrait Hans Holbein le jeune est un peintre et graveur allemand, né à Augsbourg en 1497 et décédé à Londres le 29 novembre 1543 …   Wikipédia en Français

  • Hans holbein le jeune — Hans Holbein le jeune, (1543), portrait par Lucas Horenbout d après un dessin d auto portrait Hans Holbein le jeune est un peintre et graveur allemand, né à Augsbourg en 1497 et décédé à Londres le 29 novembre 1543 …   Wikipédia en Français

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

Share the article and excerpts

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