Catamorphismes et algèbres F

J’entends donc souvent les mots “catamorphisme” et “schémas de récursivité”. De quoi s’agit-il ?

Les catamorphismes (ou cata) sont des généralisations du concept de pli en programmation fonctionnelle. Étant donné une F-algèbre et une structure de données récursive, un catamorphisme produira une valeur en évaluant récursivement votre structure de données.

Qu’est-ce qu’une F-Algèbre ? Peut-être pouvez-vous montrer quelques exemples de code en premier?

La configuration n’est pas si simple, alors commençons simplement. Supposons que vous ayez la structure de données suivante pour représenter une expression:

Et une expression simple peut ressembler à ceci:

Avoir juste une structure de données d’expression est inutile, bien sûr, vous aurez besoin d’une fonction pour évaluer et obtenir le résultat:

C’est là qu’intervient la généralisation du catamorphisme:

🤨, mais à quoi bon ? Vous appliquez simplement un argument à une fonction ?

C’est parce que c’est notReallyCata. La fonction cata réelle est générique et ne dépend d’aucune structure de données ou fonction d’évaluateur particulière. Voir, la création d’une structure de données récursive, puis son pliage est un modèle commun que cata essaie de généraliser.

Ok, alors à quoi ressemble la vraie cata?

🤯

C’est pourquoi nous avons commencé avec notReallyCata. Nous décomposerons l’implémentation plus tard jusqu’à ce qu’elle clique. Mais maintenant, continuons avec notre exemple Expression. Tout d’abord, nous devons nous débarrasser de la récursivité en introduisant un paramètre de type:

Toutes les références à Expression sont remplacées par le paramètre de type a afin que la structure de données ne soit plus récursive.

Pourquoi y a-t-il un F à la fin des constructeurs de type?

Heureux que vous ayez demandé — c’est un indice que ExpressionF peut être un Functor:

Rien d’extraordinaire, il suffit d’appliquer une fonction à la structure de préservation de la valeur enveloppée.

Je ne sais pas pourquoi nous en avons besoin 🤔

Cela n’a pas de sens maintenant, mais ce sera un peu plus tard. Maintenant, la façon dont nous créons notre expression n’a pas changé (sauf pour les noms des constructeurs):

Mais le type résultant est différent:

expr réduit tout en un seul Expression tandis que exprF encode des informations sur le niveau d’imbrication de notre arbre d’expressions. En parlant d’évaluation, voici comment nous pouvons mettre en œuvre eval pour ExpressionF:

La principale différence avec l’original evalExpr est que nous n’avons pas d’appel récursif à evalExprF (ExpressionF n’est pas récursif, rappelez-vous?). Cela signifie également que notre évaluateur ne peut travailler qu’avec une seule expression de niveau:

Et ne compilera pas à ce sujet:

Tout simplement parce que exprF expepecte ExpressionF Int et que nous bousculons ExpressionF (ExpressionF Int).

Pour que cela fonctionne, nous pourrions définir un autre évaluateur:

On dirait un peu ad hoc, que se passe-t-il si vous avez des expressions profondément imbriquées?

Oui, pour une expression imbriquée arbitraire, cette approche n’est pas évolutive — chaque niveau d’imbrication supplémentaire vous oblige à écrire une fonction spécialisée.

Il existe un moyen de généraliser cette imbrication avec un nouveau type:

Réparer? On dirait une structure de données récursive qui ne fait pas grand-chose. En quoi est-ce utile?

Regardons d’abord l’expression avant le signe égal: en effet Fix est une structure de données récursive qui a un paramètre de type f. Ce paramètre a kind * -> *, par exemple, il prend également un paramètre type. Par exemple, vous ne pouvez pas construire Fix fournissant Int ou Bool, cela doit être quelque chose comme Maybe, List ou…ExpressionF. C’est pourquoi nous avons introduit le paramètre type pour ExpressionF. Ensuite, après le signe égal, nous avons un seul constructeur de type Fx prenant un seul argument de type f (Fix f) qui est essentiellement une expression qui construit la valeur de f. Dans le cas de Maybe, ce serait Maybe (Fix Maybe) et le tout est enveloppé avec Fx dans le type Fix Maybe.

La signature de type est déroutante à lire au début car le constructeur de type peut avoir le même nom que le type lui-même plus l’auto-référencement. Mais il n’y a pas grand-chose de plus que de simplement envelopper un type d’ordre supérieur dans une structure de données. Btw, unfix est un opposé à Fx et tout ce qu’il fait est la correspondance de modèle sur Fx et renvoie une valeur enveloppée, pas grave.

Maintenant, nous allons remplacer chaque ExpressionF de notre arbre d’expression par Fix ExpressionF. Notez la différence dans la construction d’expressions avec et sans Fx — elles sont fondamentalement les mêmes, sauf que nous devons les ajouter au début Fx $:

Le type résultant d’une version “fixe” est Fix ExpressionF, nous sommes donc de retour à une représentation récursive, mais nous devons maintenant utiliser la fonction unfix pour récupérer notre structure de données non récursive.

Quels sont les avantages d’avoir Fix? On dirait que c’est la même approche que le type Expression original, mais maintenant nous avons ce non-sens Fix et unfix bizarre?

Oui, mais nous essayons de généraliser le processus de pliage, cela nécessite l’introduction d’abstractions supplémentaires, comme Fix et Algebra dont nous discuterons plus tard. Supportez-moi, ça devrait avoir plus de sens plus tard.

Nous avons donc notre structure de données “fixe”, à quoi ressemblerait la fonction d’évaluation?

Étant donné un Fix ExpressionF, la seule chose que nous pouvons en faire est d’appeler unfix qui produit ExpressionF (Fix ExpressionF):

Le ExpressionF retourné peut être l’un de nos ValueF, AddF ou MultF ayant un Fix ExpressionF comme paramètre de type. Il est logique de faire la correspondance des motifs et de décider quoi faire ensuite:

Oui, cela ressemble à notre tout premier évaluateur récursif pour Expression avec l’ajout de devoir déballer l’expression avec unfix. Alors pourquoi s’embêter avec Fix de toute façon?

Voici la clé: nous réutiliserons notre évaluateur original “sans correction” pour ExpressionF et le distribuerons d’une manière ou d’une autre sur la structure Fix ExpressionF. Cela devrait donc être une fonction prenant deux arguments — l’évaluateur et la structure à évaluer:

Essayons de comprendre l’implémentation — la première chose logique à faire est d’utiliser unfix pour obtenir ExpressionF, puis peut-être le passer à evaluator:

Évidemment, cela ne fonctionne pas, evaluator attend ExpressionF Int et non ExpressionF (Fix ExpressionF). Au fait, rappelez-vous que ExpressionF est un Functor? C’est là que cela devient pratique — nous pouvons utiliser fmap pour appliquer le même processus au niveau interne de notre arbre d’expression:

Prenez un moment et réfléchissez à ce qui se passe: nous passons une fonction récursive almostCata evaluator dans la fmap. Si l’expression actuelle est AddF ou MultF, cette fonction sera passée d’un niveau plus profond et fmap sera à nouveau appelée. Cela se produira jusqu’à ce que nous atteignions ValueF, la fmapping sur ValueF renvoie une valeur de type ExpressionF Int et c’est exactement ce que notre fonction evaluator accepte.

En regardant almostCata, nous pouvons voir qu’il n’a vraiment rien de spécifique au type ExpressionF ou Int et peut théoriquement être généralisé avec un paramètre de type f. La seule contrainte devrait être d’avoir une instance Functor pour f, car nous utilisons fmap:

Et c’est la version finale de cata. Voici l’implémentation complète avec quelques exemples d’utilisation:

Je suppose que c’est cool. Mais pourquoi?

Beaucoup de concepts en théorie des catégories et en programmation fonctionnelle sont assez abstraits et il est parfois difficile de trouver une application pratique immédiate pour certaines idées. Mais la recherche d’abstractions et de généralisations est utile pour trouver des modèles et des solutions élégantes à des problèmes qui nécessitent autrement une mise en œuvre ad hoc.

Au fait, en généralisant notre fonction ExpressionF -> Int à Functor f => (f a -> a), nous avons découvert un autre concept important appelé F-Algèbre. Fondamentalement, la F-algèbre est un triple de foncteur f, d’un type a et d’une fonction d’évaluateur f a -> a. Notez que a ici pas polymorphe — il doit s’agir d’un type concret, comme Int ou Bool et cela s’appelle un type de support. Pour n’importe quel endo-foncteur f, vous pouvez créer plusieurs F-Algèbres basées dessus. Prenons l’exemple de nos expressions – endo-foncteur f vaut ExpressionF, a vaut Int et l’évaluateur vaut evalExprF. Mais nous pouvons changer le type de porteuse et produire plus d’algèbres:

Ce sont juste des évaluateurs différents qui peuvent être transmis à cata, non?

Oui, nous choisissons différents types de transporteurs et choisissons notre implémentation. Mais là l’astuce — il y a une mère de tous les évaluateurs que nous pouvons créer en choisissant notre type de transporteur pour être…Fix ExprF.

Évaluer à Int ou Bool a tout à fait du sens, mais qu’est-ce que ce initialAlgebra évaluerait? Quand dois-je avoir Fix de quelque chose à la suite de mon évaluateur?

Bien sûr, vous n’écrirez pas quelque chose comme ça vous-même, vous voulez juste vous montrer le sens plus profond derrière les algèbres f et les cata. En fait, nous avons déjà une implémentation pour un tel évaluateur et c’est exactement Fx constructeur:

Attendez, Fx est un évaluateur? C’est dingue.

Oui et il fait la chose la plus simple que vous puissiez faire — enregistrer l’expession dans une structure de données. Alors que tous les autres évaluateurs (algebra0, algebra1) ont produit une certaine valeur en réduisant l’expression (comme faire une somme ou une concaténation) Fx enveloppe simplement l’expression sans perdre de données.

C’est pourquoi nous avons introduit Fix en premier lieu — vous évaluez d’abord votre structure de données d’origine avec Fx dans l’algèbre initiale Fix f, puis en utilisant cata l’évaluation “réelle” se produit en fmap ing votre évaluateur concret sur l’algèbre initiale.

Du point de vue de la théorie des catégories, toutes les algèbres basées sur le même endo-foncteur forment une catégorie. Cette catégorie a un objet initial qui est notre algèbre initiale créée en choisissant le type de porteuse comme Fix f. Il y a quelques excellents articles de blog de Bartosz Milewski que je recommande fortement de consulter si vous souhaitez obtenir une compréhension catégorique approfondie.

C’est encore assez difficile à comprendre, je ne pense pas bien comprendre le concept

Il vaut toujours mieux faire la main: essayez de ré-implémenter Fix et cata par vous-même, pensez aux structures de données et aux algèbres possibles. Par exemple, un String peut être représenté récursivement (sous la forme d’une tête et d’une queue Char de String), le length d’une chaîne peut être calculé avec cata. Voici quelques excellentes ressources pour en savoir plus:

• Comprendre les algèbres F et les algèbres F légèrement différentes par Bartosz Milewski
• Catamorphismes en 15 minutes par Chris Jones
• Programmation de bases de données Fonctionnelles Pures avec Types de points fixes par Rob Norris
• Catamorphismes sur le wiki Haskell
• Schémas de récursivité pratiques par Jared Tobin