Concept

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. 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 , 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, par , et qui fut dans le contexte du langage de programmation . 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 -> 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)) 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) 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) Dans la théorie des catégories, l'anamorphisme est le concept dual du catamorphisme. Une notation pour trouvée dans la littérature est .

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.