Nous donnons une série d’exemples, puis une approche plus globale des catamorphismes, dans le langage de programmation Haskell.

IterationEdit

Les prescriptions d’étape d’itération conduisent à des nombres naturels comme objet initial.

Considérons le foncteur fmaybemappant un type de données b à un type de données fmaybe b, qui contient une copie de chaque terme de b ainsi qu’un terme supplémentaire Nothing (dans Haskell, c’est ce que fait Maybe). Cela peut être codé en utilisant un terme et une fonction. Donc, une instance d’un StepAlgebra inclut également une fonction de fmaybe bb, qui mappe Nothing à un terme fixe nil de b, et où les actions sur les termes copiés seront appelées next.

List foldEdit

Pour un type fixe a, considérez le foncteur mappant les types b au type de produit de ces deux types. De plus, nous ajoutons également un terme Nil à ce type résultant. Une f-algèbre doit maintenant mapper Nil à un terme spécial nil de b ou « fusionner » une paire (tout autre terme du type construit) en un terme de b. Cette fusion d’une paire peut être codée en fonction du type a -> b -> b.

Tree foldEdit

Pour un type fixe a, considérez les types de mappage de foncteurs b à un type qui contient une copie de chaque terme de a ainsi que toutes les paires de b‘s (termes du type de produit de deux instances du type b). Une algèbre consiste en une fonction b, qui agit soit sur un terme a, soit sur deux termes b. Cette fusion d’une paire peut être codée comme deux fonctions de type a -> b resp. b -> b -> b.

Cas généraldit

Des études théoriques plus approfondies des algèbres initiales révèlent que la F-algèbre obtenue en appliquant le foncteur à sa propre algèbre initiale lui est isomorphe.

Les systèmes de type fort nous permettent de spécifier de manière abstraite l’algèbre initiale d’un foncteur f comme point fixe a =f a. Les catamorphismes définis récursivement peuvent maintenant être codés en une seule ligne, où l’analyse de cas (comme dans les différents exemples ci-dessus) est encapsulée par le fmap. Puisque le domaine de ces derniers sont des objets dans l’image de f, l’évaluation des catamorphismes va et vient entre a et f a.

Maintenant encore le premier exemple, mais maintenant en passant le foncteur Maybe à corriger. L’application répétée du foncteur Maybe génère une chaîne de types, qui peuvent cependant être unis par l’isomorphisme du théorème du point fixe. Nous introduisons le terme zero, qui provient de Nothing de Maybes et identifions une fonction successeur avec une application répétée du Just. De cette façon, les nombres naturels apparaissent.

Et maintenant encore l’exemple de l’arbre. Pour cela, nous devons fournir le type de données du conteneur d’arborescence afin de pouvoir configurer le foncteur fmap (nous n’avons pas eu à le faire pour le foncteur Maybe, car il fait partie du prélude standard).

data Tcon a b = TconL a | TconR b binstance Functor (Tcon a) where fmap f (TconL x) = TconL x fmap f (TconR y z) = TconR (f y) (f z)

type Tree a = Fix (Tcon a) -- the initial algebraend :: a -> Tree aend = Iso . TconLmeet :: Tree a -> Tree a -> Tree ameet l r = Iso $ TconR l r

treeDepth :: Algebra (Tcon a) Integer -- again, the treeDepth f-algebra exampletreeDepth (TconL x) = 1treeDepth (TconR y z) = 1 + max y z

Ce qui suit sera évalué à 4: cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))