Anamorphisme
Ne doit pas être confondu avec Anamorphose.
L'anamorphisme (du Grec: ανα- = vers le haut; morphisme = forme) est un concept de la programmation fonctionnelle fondé sur la théorie des catégories.
La notion invoquée par cet article est trop technique ou pas assez détaillée.
Il serait bien de la préciser au moyen d’un lien wiki ou d’une note.
Pour plus de renseignements, consultez Aide:Wikification et Aide:Note.
L'anamorphisme en programmation fonctionnelle
modifierEn 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 (en), et qui fut dans le contexte du langage de programmation Squiggol (en).
Exemples
modifierAnamorphismes sur des listes
modifierUn 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 -> Maybe (a,b)) -> b -> [a]
-- Définition de la fonction 'ana' :
ana unspool x = case unspool x of
Nothing -> []
Just (a,y) -> a : ana unspool y
Cet anamorphisme générique permet de définir de nombreuses fonctions. Par exemple, on peut facilement écrire l'itération d’une fonction f sous forme de liste (infinie) :
iterate :: (a -> a) -> a -> [a]
iterate f = ana (\a -> Just (a, f a))
Anamorphismes sur d'autre type de données
modifierOn 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) a (Tree a)
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
modifierDans la théorie des catégories, l'anamorphisme est le concept dual du catamorphisme.
Notation
modifierUne notation pour trouvée dans la littérature est . 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
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Anamorphism » (voir la liste des auteurs).
- (en) Erik Meijer, Maarten Fokkinga et Ross Paterson, « Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire », CiteSeerX, (lire en ligne)
