Skip to content

Que signifie "coalgebra" dans le contexte de la programmation ?

Nous vous proposons de tester cette solution dans un environnement contrôlé avant de l'envoyer en production, bravo.

Solution :

Algebras

Je pense que l'endroit pour commencer serait de comprendre l'idée d'une algèbre. C'est juste une généralisation des structures algébriques comme les groupes, les anneaux, les monoïdes et ainsi de suite. La plupart du temps, ces choses sont introduites en termes d'ensembles, mais puisque nous sommes entre amis, je vais plutôt parler de types Haskell. (Je ne peux pas résister à l'utilisation de quelques lettres grecques cependant - elles rendent tout plus cool).

Une algèbre, alors, est juste un type τ avec quelques fonctions et identités. Ces fonctions prennent des nombres différents d'arguments de type τ et produisent un τ: sans contrainte, elles ressemblent toutes à (τ, τ,…, τ) → τ. Ils peuvent aussi avoir des "identités"-éléments de τ qui ont un comportement spécial avec certaines des fonctions.

L'exemple le plus simple de ceci est le monoïde. Un monoïde est un type quelconque τ avec une fonction mappend ∷ (τ, τ) → τ et une identité mzero ∷ τ. D'autres exemples incluent des choses comme les groupes (qui sont juste comme les monoïdes, sauf avec une fonction supplémentaire invert ∷ τ → τ supplémentaire), les anneaux, les treillis et ainsi de suite.

Toutes les fonctions opèrent sur τ mais peuvent avoir des ariés différents. Nous pouvons les écrire comme suit τⁿ → ττⁿ correspond à un tuple de nτ. De cette façon, il est logique de penser aux identités en tant que τ⁰ → ττ⁰ est juste le tuple vide (). Donc, nous pouvons réellement simplifier l'idée d'une algèbre maintenant : c'est juste un certain type avec un certain nombre de fonctions sur lui.

Une algèbre est juste un modèle commun en mathématiques qui a été "factorisé", tout comme nous le faisons avec le code. Les gens ont remarqué que tout un tas de choses intéressantes - les monoïdes, les groupes, les treillis, etc. mentionnés plus haut - suivent tous un modèle similaire, alors ils l'ont abstrait. L'avantage de faire cela est le même qu'en programmation : cela crée des preuves réutilisables et rend certains types de raisonnement plus faciles.

F-Algebras

Cependant, nous n'en avons pas tout à fait fini avec la factorisation. Jusqu'à présent, nous avons un tas de fonctions... τⁿ → τ. Nous pouvons en fait faire une astuce astucieuse pour les combiner toutes en une seule fonction. En particulier, regardons les monoïdes : nous avons mappend ∷ (τ, τ) → τ et mempty ∷ () → τ. Nous pouvons les transformer en une seule fonction en utilisant un type de somme-Either. Cela ressemblerait à ceci :

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

Nous pouvons en fait utiliser cette transformation à plusieurs reprises pour combiner tous les les τⁿ → τ en une seule fonction, pour tout algèbre. (En fait, nous pouvons le faire pour n'importe quel nombre de fonctions a → τ, b → τ et ainsi de suite pour n'importe quela, b,….)

Cela nous permet de parler des algèbres comme d'un type τ avec un unique à partir d'un mélange de Eitherà une seule τ. Pour les monoïdes, ce désordre est : Either (τ, τ) (); pour les groupes (qui ont un τ → τ supplémentaire), c'est : Either (Either (τ, τ) τ) (). C'est un type différent pour chaque structure différente. Qu'ont donc tous ces types en commun ? La chose la plus évidente est qu'ils sont tous juste des sommes de produits - des types de données algébriques. Par exemple, pour les monoïdes, nous pourrions créer un type d'argument monoïde qui fonctionne pour tout monoïde τ :

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

On peut faire la même chose pour les groupes, les anneaux, les treillis et toutes les autres structures possibles.

Qu'y a-t-il d'autre de spécial dans tous ces types ? Eh bien, ils sont tous Functors! Par exemple :

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

Donc nous pouvons généraliser encore plus notre idée d'une algèbre. C'est juste un certain type τ avec une fonction f τ → τ pour un certain foncteur f. En fait, nous pourrions écrire ceci comme une classe de type :

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

On l'appelle souvent une "F-algèbre" car elle est déterminée par le foncteur F. Si nous pouvions appliquer partiellement les classes de types, nous pourrions définir quelque chose comme. class Monoid = Algebra MonoidArgument.

Coalgebras

Maintenant, espérons que vous avez une bonne compréhension de ce qu'est une algèbre et comment c'est juste une généralisation des structures algébriques normales. Alors qu'est-ce qu'une F-coalgebre ? Eh bien, le co implique qu'il s'agit du "dual" d'une algèbre, c'est-à-dire que nous prenons une algèbre et inversons certaines flèches. Je ne vois qu'une seule flèche dans la définition ci-dessus, donc je vais juste la retourner :

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

Et c'est tout ce qu'il y a ! Maintenant, cette conclusion peut sembler un peu désinvolte (heh). Elle vous dit ce que une coalgèbre est, mais ne donne pas vraiment un aperçu sur la façon dont il est utile ou pourquoi nous nous en soucions. J'y reviendrai un peu plus tard, une fois que j'aurai trouvé ou inventé un ou deux bons exemples :P.

Classes et objets

Après avoir lu un peu, je pense avoir une bonne idée de la façon d'utiliser les coalgebras pour représenter les classes et les objets. Nous avons un type C qui contient tous les états internes possibles des objets de la classe ; la classe elle-même est une coalgebrane sur C qui spécifie les méthodes et les propriétés des objets.

Comme le montre l'exemple de l'algèbre, si nous avons un tas de fonctions comme... a → τ et b → τ pour tout a, b,…nous pouvons les combiner en une seule fonction à l'aide de la fonction Eitherun type de somme. La "notion" duale serait de combiner un tas de fonctions de type τ → a, τ → b et ainsi de suite. Nous pouvons le faire en utilisant le dual d'un type somme - un type produit. Ainsi, étant donné les deux fonctions ci-dessus (appelées f et g), nous pouvons en créer une seule comme suit :

both ∷ τ → (a, b)
both x = (f x, g x)

Le type (a, a) est un foncteur de la manière directe, donc il correspond certainement à notre notion de F-coalgebra. Cette astuce particulière nous permet de regrouper un tas de fonctions différentes - ou, pour la POO, de méthodes - en une seule fonction de type τ → f τ.

Les éléments de notre type C représentent la fonction interne de l'objet. Si l'objet possède quelques propriétés lisibles, elles doivent pouvoir dépendre de l'état. La façon la plus évidente de le faire est de les rendre une fonction de C. Ainsi, si nous voulons une propriété de longueur (par ex. object.length), nous aurions une fonction C → Int.

Nous voulons des méthodes qui peuvent prendre un argument et modifier l'état. Pour cela, nous devons prendre tous les arguments et produire une nouvelle fonction C. C . Imaginons un setPosition qui prend un x et un y coordonnée : object.setPosition(1, 2). Cela ressemblerait à ceci : C → ((Int, Int) → C).

Le motif important ici est que les "méthodes" et "propriétés" de l'objet prennent l'objet lui-même comme premier argument. C'est exactement comme le self en Python et comme le paramètre implicite this implicite de nombreux autres langages. Une coalgebra ne fait essentiellement qu'encapsuler le comportement de la prise d'un paramètre self . self paramètre : c'est ce que le premier Cdans C → F C est.

Alors, mettons tout ça ensemble. Imaginons une classe avec un position propriété, une name et une propriété setPosition fonction :

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

Nous avons besoin de deux parties pour représenter cette classe. Tout d'abord, nous devons représenter l'état interne de l'objet ; dans ce cas, il contient simplement deux propriétés Ints et un String. (C'est notre type C .) Il faut ensuite trouver l'algèbre de charbon représentant la classe.

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

Nous avons deux propriétés à écrire. Elles sont assez triviales :

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

Maintenant nous devons juste être capable de mettre à jour la position :

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

C'est tout comme une classe Python avec son explicite. self variables. Maintenant que nous avons un tas de self → nous devons les combiner en une seule fonction pour la coalgebra. Nous pouvons le faire avec un simple tuple :

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

Le type ((Int, Int), String, (Int, Int) → c)-pour toutc-est un foncteur, donc coop a bien la forme que nous voulons : Functor f ⇒ C → f C.

Etant donné ceci, Cainsi que coop forment une algèbre de charbon qui spécifie la classe que j'ai donnée ci-dessus. Vous pouvez voir comment nous pouvons utiliser cette même technique pour spécifier un nombre quelconque de méthodes et de propriétés que nos objets doivent avoir.

Cela nous permet d'utiliser le raisonnement coalgébrique pour traiter les classes. Par exemple, nous pouvons faire intervenir la notion d'un "homomorphisme F-coalgébrique" pour représenter les transformations entre les classes. Il s'agit d'un terme à consonance effrayante qui signifie simplement une transformation entre coalgebras qui préserve la structure. Cela rend beaucoup plus facile de penser à la mise en correspondance de classes sur d'autres classes.

En bref, une F-coalgebra représente une classe en ayant un tas de propriétés et de méthodes qui dépendent toutes d'un...selfparamètre contenant l'état interne de chaque objet.

Autres catégories

Jusqu'à présent, nous avons parlé des algèbres et des coalgebras en tant que types Haskell. Une algèbre est juste un type τ avec une fonction f τ → τ et une coalgebra est juste un type τ avec une fonction τ → f τ.

Cependant, rien ne lie vraiment ces idées à Haskell. en soi. En fait, elles sont généralement introduites en termes d'ensembles et de fonctions mathématiques plutôt que de types et de fonctions Haskell. En effet, on peut généraliser ces concepts à tout catégories !

Nous pouvons définir une F-algèbre pour une catégorie quelconque C . D'abord, nous avons besoin d'un foncteur F : C → C-c'est-à-dire un endofuncteur. (Tout Haskell Functorsont en fait des endofonctions de Hask → Hask.) Alors, une algèbre est juste un objet A de Cavec un morphisme F A → A. Une coalgébre est la même chose, sauf avec A → F A.

Que gagnons-nous à considérer d'autres catégories ? Eh bien, nous pouvons utiliser les mêmes idées dans des contextes différents. Comme les monades. En Haskell, une monade est un certain type M ∷ ★ → ★ avec trois opérations :

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

Le map est juste une preuve du fait que M est un Functor. Donc on peut dire qu'une monade est juste un foncteur avec deux opérations : return et join.

Les foncteurs forment eux-mêmes une catégorie, les morphismes entre eux étant ce qu'on appelle des "transformations naturelles". Une transformation naturelle est juste une façon de transformer un foncteur en un autre tout en préservant sa structure. Voici un bel article aidant à expliquer l'idée. Il parle de concatqui est juste join pour les listes.

Avec les foncteurs Haskell, la composition de deux foncteurs est un foncteur lui-même. En pseudocode, on pourrait écrire ceci :

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

Cela nous aide à réfléchir sur join comme une correspondance entre f ∘ f → f. Le type de join est ∀α. f (f α) → f α. Intuitivement, on peut voir comment une fonction valable pour tous les types α peut être considéré comme une transformation de f.

return est une transformation similaire. Son type est ∀α. α → f α. Cela semble différent - le premier α n'est pas "dans" un foncteur ! Heureusement, nous pouvons corriger cela en ajoutant un foncteur d'identité à cet endroit : ∀α. Identity α → f α. Donc return est une transformation Identity → f.

Maintenant nous pouvons penser à une monade comme étant juste une algèbre basée sur un certain foncteur f avec des opérations f ∘ f → f et Identity → f. Cela ne vous semble-t-il pas familier ? C'est très similaire à un monoïde, qui était juste un certain type τ avec des opérations τ × τ → τ et () → τ.

Donc une monade est juste comme un monoïde, sauf qu'au lieu d'avoir un type, nous avons un foncteur. C'est la même sorte d'algèbre, juste dans une catégorie différente. (C'est de là que vient la phrase "Une monade est juste un monoïde dans la catégorie des endofoncteurs" pour autant que je sache).

Maintenant, nous avons ces deux opérations : f ∘ f → f et Identity → f. Pour obtenir la coalgébre correspondante, il suffit de retourner les flèches. Cela nous donne deux nouvelles opérations : f → f ∘ f et f → Identity. Nous pouvons les transformer en types Haskell en ajoutant des variables de type comme ci-dessus, ce qui nous donne ∀α. f α → f (f α) et ∀α. f α → α. Cela ressemble à la définition d'une comonade :

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)

Une comonade est donc coalgebra dans une catégorie d'endofoncteurs.

Les F-algèbres et les F-coalgébres sont des structures mathématiques qui jouent un rôle déterminant dans le raisonnement sur les sujets suivants types inductifs (ou types récursifs).

F-algèbres

Nous allons commencer par les F-algebras. Je vais essayer d'être aussi simple que possible.

Je suppose que vous savez ce qu'est un type récursif. Par exemple, c'est un type pour une liste d'entiers :

data IntList = Nil | Cons (Int, IntList)

Il est évident qu'il est récursif - en effet, sa définition se réfère à elle-même. Sa définition consiste en deux constructeurs de données, qui ont les types suivants :

Nil  :: () -> IntList
Cons :: (Int, IntList) -> IntList

Notez que j'ai écrit le type de Nil comme () -> IntListet non pas simplement IntList. Il s'agit en fait de types équivalents d'un point de vue théorique, car () type n'a qu'un seul habitant.

Si nous écrivons les signatures de ces fonctions d'une manière plus théorique ensembliste, nous obtiendrons .

Nil  :: 1 -> IntList
Cons :: Int × IntList -> IntList

1 est un ensemble unitaire (ensemble à un élément) et A × B l'opération est un produit en croix de deux ensembles A et B (c'est-à-dire l'ensemble des paires (a, b)a passe par tous les éléments de A et b passe par tous les éléments de B).

Union disjointe de deux ensembles A et B est un ensemble A | B qui est une union des ensembles {(a, 1) : a in A} et {(b, 2) : b in B}. Essentiellement, c'est un ensemble de tous les éléments des deux ensembles A et de Bmais avec chacun de ces éléments "marqués" comme appartenant soit à A soit à BAinsi, lorsque nous choisissons un élément de la liste A | B nous saurons immédiatement si cet élément provient de A ou de B.

Nous pouvons "joindre Nil et Cons afin qu'elles forment une seule fonction travaillant sur un ensemble 1 | (Int × IntList):

Nil|Cons :: 1 | (Int × IntList) -> IntList

En effet, si Nil|Cons est appliquée à () (qui, évidemment, appartient à 1 | (Int × IntList) set), alors elle se comporte comme si elle était Nil; si Nil|Cons est appliqué à toute valeur de type (Int, IntList) (de telles valeurs sont également dans l'ensemble 1 | (Int × IntList)il se comporte comme Cons.

Considérons maintenant un autre type de données :

data IntTree = Leaf Int | Branch (IntTree, IntTree)

Il possède les constructeurs suivants :

Leaf   :: Int -> IntTree
Branch :: (IntTree, IntTree) -> IntTree

qui peuvent aussi être réunis en une seule fonction :

Leaf|Branch :: Int | (IntTree × IntTree) -> IntTree

On peut voir que ces deux joined ont un type similaire : elles ressemblent toutes deux à

f :: F T -> T

F est une sorte de transformation qui prend notre type et donne un type plus complexe, qui consiste en x et | les opérations, les utilisations de T et éventuellement d'autres types. Par exemple, pour IntList et IntTreeF se présente comme suit :

F1 T = 1 | (Int × T)
F2 T = Int | (T × T)

Nous pouvons immédiatement remarquer que tout type algébrique peut être écrit de cette manière. En effet, c'est pour cela qu'ils sont dits " algébriques " : ils sont constitués d'un certain nombre de " sommes " (unions) et de " produits " (produits croisés) d'autres types.

Nous pouvons maintenant définir la F-algèbre. F-algèbre est juste une paire (T, f)T est un type quelconque et f est une fonction de type f :: F T -> T. Dans nos exemples, les algèbres F sont (IntList, Nil|Cons) et (IntTree, Leaf|Branch). Notez cependant que, malgré ce type de f la fonction est la même pour chaque F, T et f peuvent elles-mêmes être arbitraires. Par exemple, (String, g :: 1 | (Int x String) -> String) ou (Double, h :: Int | (Double, Double) -> Double) pour certains g et h sont également des F-algèbres pour F correspondant.

Ensuite, nous pouvons introduire homomorphismes de F-algèbres et ensuite F-algèbres initiales qui ont des propriétés très utiles. En effet , (IntList, Nil|Cons) est une algèbre F1 initiale, et (IntTree, Leaf|Branch) est une algèbre F2 initiale. Je ne présenterai pas les définitions exactes de ces termes et propriétés car elles sont plus complexes et abstraites que nécessaire.

Néanmoins, le fait que, disons, (IntList, Nil|Cons) est une F-algèbre nous permet de définir fold-sur ce type. Comme vous le savez, le pliage est une sorte d'opération qui transforme un type de données récursif en une valeur finie. Par exemple, nous pouvons plier une liste d'entiers en une seule valeur qui est une somme de tous les éléments de la liste :

foldr (+) 0 [1, 2, 3, 4] -> 1 + 2 + 3 + 4 = 10

Il est possible de généraliser une telle opération sur n'importe quel type de données récursif.

Ce qui suit est une signature de foldr fonction :

foldr :: ((a -> b -> b), b) -> [a] -> b

Notez que j'ai utilisé des accolades pour séparer les deux premiers arguments du dernier. Ceci n'est pas réel foldr mais elle lui est isomorphe (c'est-à-dire que vous pouvez facilement obtenir l'une à partir de l'autre et vice versa). Partiellement appliquée foldr aura la signature suivante :

foldr ((+), 0) :: [Int] -> Int

On voit que c'est une fonction qui prend une liste d'entiers et renvoie un seul entier. Définissons une telle fonction en fonction de notre fonction IntList type.

sumFold :: IntList -> Int
sumFold Nil         = 0
sumFold (Cons x xs) = x + sumFold xs

Nous voyons que cette fonction se compose de deux parties : la première partie définit le comportement de cette fonction sur le type Nil .Nilpartie de IntListet la seconde partie définit le comportement de la fonction sur la partie Cons partie.

Supposons maintenant que nous programmons non pas en Haskell mais dans un langage qui permet l'utilisation de types algébriques directement dans les signatures de type (bon, techniquement, Haskell permet l'utilisation de types algébriques via des tuples et des Either a b mais cela conduira à une verbosité inutile). Considérons une fonction :

reductor :: () | (Int × Int) -> Int
reductor ()     = 0
reductor (x, s) = x + s

On peut voir que reductor est une fonction de type F1 Int -> Int, tout comme dans la définition de la F-algèbre ! En effet, la paire (Int, reductor) est une algèbre F1.

Parce que IntList est une algèbre F1 initiale, pour chaque type T et pour chaque fonction r :: F1 T -> T il existe une fonction, appelée catamorphisme pour rqui convertit IntList en Tet une telle fonction est unique. En effet, dans notre exemple, un catamorphisme pour reductor est sumFold. Notez comment reductor et sumFold sont similaires : ils ont presque la même structure ! Dans reductor la définition s l'utilisation du paramètre (dont le type correspond à T) correspond à l'utilisation du résultat du calcul de sumFold xs dans sumFold définition.

Juste pour rendre les choses plus claires et vous aider à voir le schéma, voici un autre exemple, et nous partons à nouveau de la fonction de pliage résultante. Considérons append la fonction qui ajoute son premier argument au second :

(append [4, 5, 6]) [1, 2, 3] = (foldr (:) [4, 5, 6]) [1, 2, 3] -> [1, 2, 3, 4, 5, 6]

Voici comment cela se présente sur notre IntList:

appendFold :: IntList -> IntList -> IntList
appendFold ys ()          = ys
appendFold ys (Cons x xs) = x : appendFold ys xs

Encore une fois, essayons d'écrire le réducteur :

appendReductor :: IntList -> () | (Int × IntList) -> IntList
appendReductor ys ()      = ys
appendReductor ys (x, rs) = x : rs

appendFold est un catamorphisme pour appendReductor qui transforme IntList en IntList.

Donc, essentiellement, les algèbres F nous permettent de définir des " plis " sur les structures de données récursives, c'est-à-dire des opérations qui réduisent nos structures à une certaine valeur.

F-coalgebras

Les F-coalgébras sont des termes dits "duaux" pour les F-algébras. Elles nous permettent de définir unfolds pour des types de données récursifs, c'est-à-dire une façon de construire des structures récursives à partir d'une certaine valeur.

Supposons que vous ayez le type suivant :

data IntStream = Cons (Int, IntStream)

Il s'agit d'un flux infini d'entiers. Son seul constructeur a le type suivant :

Cons :: (Int, IntStream) -> IntStream

Ou, en termes d'ensembles

Cons :: Int × IntStream -> IntStream

Haskell vous permet de faire du pattern matching sur les constructeurs de données, vous pouvez donc définir les fonctions suivantes travaillant sur . IntStreams :

head :: IntStream -> Int
head (Cons (x, xs)) = x

tail :: IntStream -> IntStream
tail (Cons (x, xs)) = xs

Vous pouvez naturellement "joindre" ces fonctions en une seule fonction de type IntStream -> Int × IntStream:

head&tail :: IntStream -> Int × IntStream
head&tail (Cons (x, xs)) = (x, xs)

Remarquez comment le résultat de la fonction coïncide avec la représentation algébrique de notre fonction IntStream type. On peut faire la même chose pour d'autres types de données récursives. Peut-être avez-vous déjà remarqué le schéma. Je fais référence à une famille de fonctions de type

g :: T -> F T

T est un certain type. A partir de maintenant, nous définirons

F1 T = Int × T

Maintenant, F-coalgebra est une paire (T, g)T est un type et g est une fonction de type g :: T -> F T. Par exemple, (IntStream, head&tail) est une coalgebre F1. Encore une fois, c'est comme pour les F-algèbres, g et T peuvent être arbitraires, par exemple,(String, h :: String -> Int x String) est aussi une coalgebre F1 pour un certain h.

Parmi tous les F-coalgebras, il y a les soi-disant F-coalgebras terminales qui sont duales aux F-algèbres initiales. Par exemple , IntStream est une F-algèbre terminale. Cela signifie que pour tout type T et pour chaque fonction p :: T -> F1 T il existe une fonction, appelée anamorphisme, qui convertit T en IntStreamet cette fonction est unique.

Considérons la fonction suivante, qui génère un flux d'entiers successifs à partir de celui donné :

nats :: Int -> IntStream
nats n = Cons (n, nats (n+1))

Maintenant, inspectons une fonction natsBuilder :: Int -> F1 Int, c'est-à-dire , natsBuilder :: Int -> Int × Int:

natsBuilder :: Int -> Int × Int
natsBuilder n = (n, n+1)

Encore une fois, nous pouvons voir une certaine similitude entre nats et natsBuilder. C'est très similaire à la connexion que nous avons observée avec les réducteurs et les plis plus tôt. nats est un anamorphisme pour natsBuilder.

Autre exemple, une fonction qui prend une valeur et une fonction et renvoie un flux d'applications successives de la fonction à la valeur :

iterate :: (Int -> Int) -> Int -> IntStream
iterate f n = Cons (n, iterate f (f n))

Sa fonction constructrice est la suivante :

iterateBuilder :: (Int -> Int) -> Int -> Int × Int
iterateBuilder f n = (n, f n)

Puis iterate est un anamorphisme pour iterateBuilder.

Conclusion

Donc, en résumé, les F-algébriques permettent de définir des folds, c'est-à-dire des opérations qui réduisent une structure récursive en une seule valeur, et les F-coalgébriques permettent de faire l'inverse : construire un [potentially] structure infinie à partir d'une seule valeur.

En fait, en Haskell, les F-algébriques et les F-coalgébriques coïncident. C'est une très belle propriété qui est une conséquence de la présence de la valeur 'bottom' dans chaque type. Ainsi, en Haskell, les plis et les déplis peuvent être créés pour chaque type récursif. Cependant, le modèle théorique derrière cela est plus complexe que celui que j'ai présenté ci-dessus, donc je l'ai délibérément évité.

J'espère que cela vous aidera.

En parcourant le papier du tutoriel Un tutoriel sur les (co)algèbres et la (co)induction. devrait vous donner un aperçu de la co-algèbre en informatique.

Vous en trouverez ci-dessous une citation pour vous en convaincre,

En termes généraux, un programme dans un certain langage de programmation manipule des données. Au cours du
développement de l'informatique au cours des dernières décennies, il est devenu clair qu'une description abstraite
description de ces données est souhaitable, par exemple pour s'assurer que son programme ne dépend pas de la représentation particulière des données sur lesquelles il opère. De plus, une telle abstraction facilite les preuves de correction.
Cette volonté a conduit à l'utilisation de méthodes algébriques en informatique, dans une branche appelée spécification algébrique ou théorie des types de données abstraits. L'objet d'étude sont les types de données en eux-mêmes, en utilisant des notions de techniques qui sont familières de l'algèbre. Les types de données utilisés par les informaticiens sont souvent générés à partir d'une collection donnée d'opérations (constructeurs),et c'est pour cette raison que l'"initialité" des algèbres joue un rôle si important.
Les techniques algébriques standard se sont avérées utiles pour capturer divers aspects essentiels des structures de données utilisées en informatique. Mais il s'est avéré difficile de décrire algébriquement certaines des structures intrinsèquement dynamiques apparaissant en informatique. Ces structures impliquent généralement une notion d'état, qui peut être transformée de diverses manières. Les approches formelles de ces systèmes dynamiques basés sur l'état font généralement appel à des automates ou à des systèmes de transition, comme premières références classiques.
Au cours de la dernière décennie, on a progressivement compris que de tels systèmes basés sur l'état ne devraient pas être décrits comme des algèbres, mais comme ce que l'on appelle des co-algèbres. Celles-ci sont le dual formel des algèbres, d'une manière qui sera précisée dans ce tutoriel. La double propriété de l'"initialité" des algèbres, à savoir la finalité, s'est avérée cruciale pour ces coalgèbres. Et le principe de raisonnement logique qui est nécessaire pour de telles coalgèbres finales n'est pas l'induction mais la co-induction.


Prélude, à propos de la théorie des catégories.
La théorie des catégories devrait être renommée théorie des foncteurs.
Car les catégories sont ce que l'on doit définir pour définir les foncteurs.
(De plus, les foncteurs sont ce que l'on doit définir pour définir les transformations naturelles).

Qu'est-ce qu'un foncteur ?
C'est une transformation d'un ensemble vers un autre en préservant leur structure.
(Pour plus de détails, il y a beaucoup de bonnes descriptions sur le net).

Qu'est ce qu'une F-algèbre ?
C'est l'algèbre des foncteurs.
C'est juste l'étude de la propriété universelle du foncteur.

Comment peut-elle être liée à l'informatique ?
Un programme peut être vu comme un ensemble structuré d'informations.
L'exécution du programme correspond à la modification de cet ensemble structuré d'informations.
Il semble bon que l'exécution préserve la structure du programme.
Alors l'exécution peut être vue comme l'application d'un foncteur sur cet ensemble d'informations.
(Celui qui définit le programme).

Pourquoi une F-co-algèbre ?
Les programmes sont duaux par essence car ils sont décrits par des informations et ils agissent sur celles-ci.
Alors principalement les informations qui composent les programmes et les font changer peuvent être vues de deux façons.

  • Les données qui peuvent être définies comme les informations traitées par le programme.
  • L'état qui peut être défini comme l'information étant partagée par le programme.

Alors à ce stade, je voudrais dire que,

  • La F-algèbre est l'étude des transformations functorielles agissant sur l'Univers de Data (tel qu'il a été défini ici).
  • F-co-algèbres est l'étude de la transformation functorielle agissant sur l'Univers de l'État (comme cela a été défini ici).

Pendant la vie d'un programme, les données et l'état coexistent, et se complètent.
Ils sont doubles.

Nous vous montrons les critiques et les notes des lecteurs

Vous pouvez ajouter de la valeur à notre contenu en ajoutant votre expérience dans les clarifications.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.