Catamorphisme

En programmation fonctionnelle , le concept de catamorphisme (du grec ancien : κατά « vers le bas » et μορφή « forme ») désigne l' homomorphisme unique d'une algèbre initiale vers une autre algèbre.

Les catamorphismes fournissent des généralisations de replis de listes à des types de données algébriques arbitraires , qui peuvent être décrits comme des algèbres initiales . Le concept dual est celui d' anamorphisme qui généralise les dépliages . Un hylémorphisme est la composition d'un anamorphisme suivi d'un catamorphisme.

Considérons une -algèbre initiale pour un endofoncteur d'une certaine catégorie dans lui-même. Voici un morphisme de à . Comme il est initial, nous savons que chaque fois que est une autre -algèbre, c'est-à-dire un morphisme de à , il existe un unique homomorphisme de à . Par définition de la catégorie de -algèbre, cela correspond à un morphisme de à , conventionnellement noté aussi , tel que . Dans le contexte de -algèbre, le morphisme spécifié de manière unique à partir de l'objet initial est noté par et donc caractérisé par la relation suivante :

Une autre notation trouvée dans la littérature est . Les crochets ouverts utilisés sont connus sous le nom de crochets bananes , après quoi les catamorphismes sont parfois appelés bananes , comme mentionné dans Erik Meijer et al . L'une des premières publications à introduire la notion de catamorphisme dans le contexte de la programmation était l'article « Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire », par Erik Meijer et al. , qui était dans le contexte du formalisme de Squiggol . La définition catégorique générale a été donnée par Grant Malcolm.

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

Considérez le foncteur Maybedéfini dans le code Haskell ci-dessous :

données Peut-être a = Rien | Juste un type -- Peut-être
classe Functor f où -- classe pour les foncteurs fmap :: ( a -> b ) -> ( f a -> f b ) -- action du foncteur sur les morphismes
instance Functor Maybe où -- transforme Maybe en un foncteur fmap g Nothing = Nothing fmap g ( Just x ) = Just ( g x )

L'objet initial de la Maybe-Algebra est l'ensemble de tous les objets de type entier naturel Natainsi que le morphisme inidéfini ci-dessous :

données Nat = zéro | Succ Nat -- type de nombre naturel
ini :: Maybe Nat -> Nat -- objet initial de Maybe-algebra (avec un léger abus de notation) ini Rien = Zéro ini ( Juste n ) = Succ n

La catacarte peut être définie comme suit :

cata :: ( Peut-être b -> b ) -> ( Nat -> b ) cata g Zéro = g ( fmap ( cata g ) Rien ) -- Remarque : fmap (cata g) Rien = g Rien et Zéro = ini(Rien) cata g ( Succ n ) = g ( fmap ( cata g ) ( Juste n )) -- Remarque : fmap (cata g) ( Juste n ) = Juste (cata gn) et Succ n = ini( Juste n )

À titre d’exemple, considérons le morphisme suivant :

g :: Peut-être String -> String g Rien = "allez !" g ( juste str ) = "attendez..." ++ str

Ensuite, cata g ((Succ. Succ . Succ) Zero)cela sera évalué comme « attendez... attendez... attendez... allez ! ».

Pour un type fixe, aconsidérons le foncteur MaybeProd adéfini par ce qui suit :

données MaybeProd a b = Rien | Juste ( a , b ) -- (a, b) est le type de produit de a et b
classe Functor f où -- classe pour les foncteurs fmap :: ( a -> b ) -> ( f a -> f b ) -- action du foncteur sur les morphismes
instance Functor ( MaybeProd a ) où -- transforme MaybeProd a en foncteur, la fonctorialité est uniquement dans la deuxième variable de type fmap g Nothing = Nothing fmap g ( Just ( x , y )) = Just ( x , g y )

L'algèbre initiale de MaybeProd aest donnée par les listes d'éléments de type aavec le morphisme inidéfini ci-dessous :

données Liste a = EmptyList | Cons a ( Liste a )
ini :: MaybeProd a ( List a ) -> List a -- algèbre initiale de MaybeProd a ini Nothing = EmptyList ini ( Just ( n , l )) = Cons n l

La catacarte peut être définie par :

cata :: ( MaybeProd a b -> b ) -> ( List a -> b ) cata g EmptyList = g ( fmap ( cata g ) Rien ) -- Remarque : ini Rien = EmptyList cata g ( Cons s l ) = g ( fmap ( cata g ) ( Juste ( s , l ))) -- Remarque : Cons sl = ini (Juste (s,l))

Notez également que cata g (Cons s l) = g (Just (s, cata g l)). À titre d'exemple, considérons le morphisme suivant :

g :: MaybeProd Int Int -> Int g Rien = 3 g ( Juste ( x , y )) = x * y

cata g (Cons 10 EmptyList)est évalué à 30. Ceci peut être vu en développant cata g (Cons 10 EmptyList)=g (Just (10,cata g EmptyList)) = 10* cata g EmptyList=10* g Nothing=10*3.

De la même manière, il peut être démontré que cela cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList)))sera évalué à 10*(100*(1000*3))=3.000.000.

La catacarte est étroitement liée au repli à droite (voir Repli (fonction d'ordre supérieur) ) des listes foldrList. Le morphisme liftdéfini par

lift :: ( a -> b -> b ) -> b -> ( MaybeProd a b -> b ) lift g b0 Rien = b0 lift g b0 ( Juste ( x , y )) = g x y

se rapporte cataau pli droit foldrListdes listes via :

foldrList :: ( a -> b -> b ) -> b -> Liste a -> b foldrList fun b0 = cata ( lift fun b0 )

La définition de cataimplique que foldrListc'est le pli droit et non le pli gauche. Par exemple : foldrList (+) 1 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))sera évalué à 1111 et foldrList (*) 3 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))à 3.000.000.

Pour un type fixe a, considérons le foncteur mappant les types bà un type qui contient une copie de chaque terme de aainsi que toutes les paires de b(termes du type produit de deux instances du type b). Une algèbre se compose d'une fonction à b, qui agit soit sur un aterme, soit sur deux btermes. Cette fusion d'une paire peut être codée comme deux fonctions de type a -> bresp. b -> b -> b.

type TreeAlgebra a b = ( a -> b , b -> b -> b ) -- la fonction "deux cas" est codée comme (f, g) données Tree a = Leaf a | Branch ( Tree a ) ( Tree a ) -- qui s'avère être l'algèbre initiale foldTree :: TreeAlgebra a b -> ( Tree a -> b ) -- les catamorphismes sont mappés de (Tree a) à b foldTree ( f , g ) ( Leaf x ) = f x foldTree ( f , g ) ( Branch left right ) = g ( foldTree ( f , g ) left ) ( foldTree ( f , g ) right )

treeDepth :: TreeAlgebra a Integer -- une f-algèbre pour les nombres, qui fonctionne pour tout type d'entrée treeDepth = ( const 1 , \ i j -> 1 + max i j ) treeSum :: ( Num a ) => TreeAlgebra a a -- une f-algèbre, qui fonctionne pour tout type de nombre treeSum = ( id , ( + ))

Des études théoriques de catégorie plus approfondies sur les 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 types forts nous permettent de spécifier de manière abstraite l'algèbre initiale d'un foncteur fcomme son point fixe a = fa . Les catamorphismes définis de manière récursive peuvent maintenant être codés sur une seule ligne, où l'analyse des cas (comme dans les différents exemples ci-dessus) est encapsulée par la fmap. Comme le domaine de ces derniers sont des objets à l'image de f, l'évaluation des catamorphismes saute d'avant en arrière entre aet f a.

type Algebra f a = f a -> a -- les f-algèbres génériques
newtype Fix f = Iso { invIso :: f ( Fix f ) } -- nous donne l'algèbre initiale pour le foncteur f
cata :: Functor f => Algebra f a -> ( Fix f -> a ) -- catamorphisme de Fix f vers a cata alg = alg . fmap ( cata alg ) . invIso -- notez que invIso et alg se mappent dans des directions opposées

Reprenons maintenant le premier exemple, mais en passant le foncteur Maybe à Fix. 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 Maybe Nothinget identifions une fonction successeur avec l'application répétée du Just. De cette façon, les nombres naturels apparaissent.

type Nat = Fix Maybe zero :: Nat zero = Iso Nothing -- chaque 'Maybe a' a un terme Nothing, et Iso le mappe dans un successeur :: Nat -> Nat successor = Iso . Just -- Just mappe a sur 'Maybe a' et Iso le mappe à nouveau sur un nouveau terme

pleaseWait :: Algebra Maybe String -- encore l'exemple idiot d'algèbre f ci-dessus pleaseWait ( Just string ) = "wait.. " ++ string pleaseWait Nothing = "go!"

Encore une fois, ce qui suit sera évalué comme « attendez… attendez… attendez… attendez… allez ! » :cata pleaseWait (successor.successor.successor.successor $ zero)

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

données Tcon a b = TconL a | TconR b b instance Functor ( Tcon a ) où fmap f ( TconL x ) = TconL x fmap f ( TconR y z ) = TconR ( f y ) ( f z )

type Tree a = Fix ( Tcon a ) -- l'algèbre initiale end :: a -> Tree a end = Iso . TconL meet :: Tree a -> Tree a -> Tree a meet l r = Iso $ TconR l r

treeDepth :: Algebra ( Tcon a ) Integer -- encore une fois, l'exemple de f-algèbre treeDepth treeDepth ( TconL x ) = 1 treeDepth ( TconR y z ) = 1 + max y z

Les éléments suivants seront évalués à 4 :cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))