Que signifie «coalgebra» dans le contexte de la programmation?

J’ai entendu le terme «coalgearm» à plusieurs resockets dans la functional programming et dans les cercles PLT, en particulier lorsque la discussion porte sur des objects, des comonads, des objectives et autres. Googler ce terme donne des pages qui donnent une description mathématique de ces structures, ce qui est à peu près incompréhensible pour moi. Quelqu’un peut-il s’il vous plaît expliquer ce que signifient les coalgearm dans le contexte de la programmation, quelle est leur signification et comment sont-ils liés aux objects et aux comonads?

    Algèbres

    Je pense que le sharepoint départ serait de comprendre l’idée d’une algèbre . Ceci est juste une généralisation des structures algébriques telles que les groupes, les anneaux, les monoïdes, etc. La plupart du temps, ces choses sont présentées en termes d’ensembles, mais puisque nous sums entre amis, je parlerai plutôt des types Haskell. (Je ne peux pas m’empêcher d’utiliser des lettres grecques, elles rendent tout plus cool!)

    Une algèbre n’est donc qu’un type τ avec certaines fonctions et identités. Ces fonctions prennent des nombres différents d’arguments de type τ et produisent un τ : non courbé, elles ressemblent toutes à (τ, τ,…, τ) → τ . Ils peuvent aussi avoir des “identités” – des éléments de τ qui ont un comportement particulier avec certaines fonctions.

    L’exemple le plus simple est le monoïde. Un monoïde est n’importe quel type τ avec une fonction mappend ∷ (τ, τ) → τ et une identité mzero ∷ τ . D’autres exemples incluent des choses comme les groupes (qui sont comme les monoïdes sauf avec une fonction d’ invert ∷ τ → τ supplémentaire), des anneaux, des réseaux, etc.

    Toutes les fonctions opèrent sur τ mais peuvent avoir différentes arités. Nous pouvons les écrire comme τⁿ → τ , où τⁿ correspond à un tuple de n τ . De cette façon, il est logique de considérer les identités comme τ⁰ → ττ⁰ est juste le tuple vide () . Nous pouvons donc simplifier l’idée d’une algèbre maintenant: c’est juste un type avec un certain nombre de fonctions.

    Une algèbre n’est qu’un modèle courant en mathématiques qui a été “exclu”, 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 réseaux, etc. – mentionnés ci-dessus, suivaient tous un schéma similaire, alors ils ont fait abstraction. L’avantage de cela est le même qu’en programmation: il crée des épreuves réutilisables et facilite certains types de raisonnement.

    F-Algèbres

    Cependant, nous n’avons pas tout à fait fini avec l’affacturage. Jusqu’à présent, nous avons un tas de fonctions τⁿ → τ . Nous pouvons en fait faire une astuce pour les combiner en une seule fonction. En particulier, regardons les mappend ∷ (τ, τ) → τ : on a mappend ∷ (τ, τ) → τ et mempty ∷ () → τ . Nous pouvons les transformer en une fonction unique en utilisant un type de sum – Either . Cela ressemblerait à ceci:

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

    Nous pouvons effectivement utiliser cette transformation à plusieurs resockets pour combiner toutes les fonctions τⁿ → τ en une seule, pour toute algèbre. (En fait, nous pouvons le faire pour un nombre quelconque de fonctions a → τ , b → τ et ainsi de suite pour tout a, b,… .)

    Cela nous permet de parler d’algèbres sous la forme d’un type τ avec une seule fonction allant d’un désordre de l’un Either à un seul τ . Pour les monoides, ce gâchis est: Either (τ, τ) () ; pour les groupes (qui ont une opération supplémentaire τ → τ ), c’est: Either (Either (τ, τ) τ) () . C’est un type différent pour chaque structure différente. Alors, qu’est-ce que tous ces types ont en commun? La chose la plus évidente est qu’elles ne sont que des sums de produits – des types de données algébriques. Par exemple, pour les monoides, nous pourrions créer un type d’argument monoïde qui fonctionne pour n’importe quel monoï τ:

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

    Nous pouvons faire la même chose pour les groupes, les anneaux et les réseaux et toutes les autres structures possibles.

    Quelle est la particularité de tous ces types? Eh bien, ils sont tous des Functors ! Par exemple:

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

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

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

    Ceci est souvent appelé une “algèbre F” car il est déterminé par le foncteur F Si nous pouvions appliquer partiellement des classes de types, nous pourrions définir quelque chose comme la class Monoid = Algebra MonoidArgument .

    Coalgearm

    Maintenant, j’espère 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-coalgebra? Eh bien, le co implique que c’est le “dual” d’une algèbre – c’est-à-dire que nous prenons une algèbre et que nous lançons des flèches. Je ne vois qu’une seule flèche dans la définition ci-dessus, alors je vais juste retourner ça:

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

    Et c’est tout ce que c’est! Maintenant, cette conclusion peut sembler un peu désinvolte (heh). Il vous indique ce qu’est une coalgebra, mais ne donne pas vraiment un aperçu de son utilité ou de nos préoccupations. J’y reviendrai un peu, une fois que j’aurai trouvé ou trouvé un bon exemple ou deux: P.

    Classes et Objets

    Après avoir lu quelques mots, je pense avoir une bonne idée de l’utilisation des coalgearm pour représenter des classes et des objects. Nous avons un type C qui contient tous les états internes possibles des objects de la classe; la classe elle-même est une coalgebra sur C qui spécifie les méthodes et les propriétés des objects.

    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 en utilisant Either , un type sum. La double “notion” associerait un tas de fonctions de type τ → a , τ → b , etc. Nous pouvons le faire en utilisant le dual d’un type sum – un type de produit. Donc, é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 = (fx, gx) 

    Le type (a, a) est un foncteur simple, donc il correspond certainement à notre notion de F-coalgebra. Cette astuce nous permet de regrouper un ensemble de fonctions différentes – ou, pour les méthodes OOP, en une seule fonction de type τ → f τ .

    Les éléments de notre type C représentent l’état interne de l’object. Si l’object a des propriétés lisibles, il doit pouvoir dépendre de l’état. La manière la plus évidente de le faire est de les transformer en C Donc, si nous voulons une propriété de longueur (par exemple object.length ), nous aurons une fonction C → Int .

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

    Le motif important ici est que les “méthodes” et les “propriétés” de l’object prennent l’object comme premier argument. Ceci est juste comme le paramètre self dans Python et comme l’implicite de beaucoup d’autres langages. Une coalgebra encapsule essentiellement le comportement de prendre un paramètre self : c’est ce que le premier C dans C → FC est.

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

     class C private x, y : Int _name : Ssortingng public name : Ssortingng 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’object; dans ce cas, il ne contient que deux Int et une Ssortingng . (Ceci est notre type C ). Ensuite, nous devons trouver la coalgebra représentant la classe.

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

    Nous avons deux propriétés à écrire. Ils sont assez sortingviaux:

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

    Maintenant, il suffit de pouvoir mettre à jour la position:

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

    Ceci est juste comme une classe Python avec ses variables self explicites. Maintenant que nous avons un tas de fonctions self → , nous devons les combiner en une seule fonction pour la coalgebra. Nous pouvons le faire avec un simple tuple:

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

    Le type ((Int, Int), Ssortingng, (Int, Int) → c) – pour tout c – est un foncteur, donc coop a la forme que nous voulons: Functor f ⇒ C → f C

    Compte tenu de cela, C avec coop forme une coalgebra 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 pour nos objects.

    Cela nous permet d’utiliser le raisonnement Coalgebraic pour traiter les classes. Par exemple, nous pouvons introduire la notion d’homomorphisme F-coalgebra pour représenter les transformations entre classes. C’est un terme effrayant qui signifie simplement une transformation entre des coalgearm qui préservent la structure. Cela rend beaucoup plus facile la reflection sur la correspondance des classes avec d’autres classes.

    En bref, une F-coalgebra représente une classe en ayant un groupe de propriétés et de méthodes qui dépendent toutes d’un paramètre self contenant l’état interne de chaque object.

    Autres catégories

    Jusqu’à présent, nous avons parlé des algèbres et des coalgearm 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, ils sont généralement introduits en termes d’ensembles et de fonctions mathématiques plutôt que de types et de fonctions Haskell. En effet, nous pouvons généraliser ces concepts à toutes les catégories!

    Nous pouvons définir une algèbre F pour certaines catégories C Tout d’abord, nous avons besoin d’un foncteur F : C → C c’est-à-dire un endofuncteur . (Tous les Functor Haskell sont en fait des Hask → Hask de Hask → Hask .) Alors, une algèbre n’est qu’un object A de C avec un morphisme FA → A Une coalgebra est la même sauf avec A → FA .

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

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

    La fonction de map est juste une preuve du fait que M est un Functor . On peut donc dire qu’une monade est juste un foncteur avec deux opérations: return et join .

    Les foncteurs forment une catégorie eux-mêmes, les morphismes entre eux étant appelés “transformations naturelles”. Une transformation naturelle n’est qu’un moyen de transformer un foncteur en un autre tout en préservant sa structure. Voici un article intéressant qui explique l’idée. Il parle de concat , qui est juste une join pour les listes.

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

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

    Cela nous aide à penser à la join tant que mappage à partir de f ∘ f → f . Le type de join est ∀α. f (f α) → f α ∀α. f (f α) → f α . Intuitivement, on peut voir comment une fonction valide pour tous les types α peut être considérée comme une transformation de f .

    return est une transformation similaire. Son type est ∀α. α → f α ∀α. α → f α . Cela semble différent – le premier α n’est pas “dans” un foncteur! Heureusement, nous pouvons y remédier en ajoutant un foncteur d’identité: ∀α. Identity α → f α ∀α. Identity α → f α . Donc, return est une transformation Identity → f .

    Maintenant, on peut penser à une monade comme une algèbre basée sur un foncteur f avec des opérations f ∘ f → f et Identity → f . N’est-ce pas familier? C’est très similaire à un monoïde, qui était juste un 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 le même genre d’algèbre, juste dans une catégorie différente. (C’est ici que la phrase “Une monade est juste un monoïde dans la catégorie des endofuncteurs” vient de ce que je sais.)

    Maintenant, nous avons ces deux opérations: f ∘ f → f et Identity → f . Pour obtenir la coalgebra 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 α) ∀α. f α → f (f α) et ∀α. f α → α ∀α. f α → α . Cela ressemble à la définition d’une comonad:

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

    Une comonad est donc une coalgebra dans une catégorie d’endofuncteurs.

    Les algèbres F et F-coalgearm sont des structures mathématiques qui consortingbuent à raisonner sur les types inductifs (ou les types récursifs ).

    F-algèbres

    Nous allons commencer par les algèbres F. Je vais essayer d’être aussi simple que possible.

    Je suppose que vous savez ce qu’est un type récursif. Par exemple, il s’agit d’un type pour une liste d’entiers:

     data IntList = Nil | Cons (Int, IntList) 

    Il est évident qu’elle est récursive – en fait, 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 tant que () -> IntList , pas simplement IntList . Ce sont en fait des types équivalents du sharepoint vue théorique, car le type () n’a qu’un seul habitant.

    Si nous écrivons des signatures de ces fonctions de manière plus théorique, nous obtiendrons

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

    1 est un ensemble d’unités (défini avec un élément) et A × B est un produit croisé de deux ensembles A et B (c’est-à-dire, un ensemble de paires (a, b) passant par tous les éléments de A et b à travers tous les éléments de B ).

    L’union disjointe de deux ensembles A et B est un ensemble A | B A | B qui est une union d’ensembles {(a, 1) : a in A} et {(b, 2) : b in B} . Essentiellement, il s’agit d’un ensemble de tous les éléments à la fois de A et de B , mais chacun de ces éléments est “marqué” comme appartenant à A ou à B , donc lorsque nous choisissons un élément de A | B A | B nous saurons immédiatement si cet élément provient de A ou de B

    Nous pouvons «rejoindre» les fonctions Nil et Cons , afin de former une fonction unique travaillant sur un ensemble 1 | (Int × IntList) 1 | (Int × IntList) :

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

    En effet, si la fonction Nil|Cons est appliquée à la valeur () (qui, de toute évidence, appartient à 1 | (Int × IntList) ), alors elle se comporte comme si elle était Nil ; si Nil|Cons est appliqué à toute valeur de type (Int, IntList) (ces 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 a les constructeurs suivants:

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

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

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

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

     f :: FT -> T 

    F est une sorte de transformation qui prend notre type et donne un type plus complexe, qui consiste en x et | opérations, usages de T et éventuellement d’autres types. Par exemple, pour IntList et IntTree F IntTree 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, ils sont appelés «algébriques»: ils consistent en un certain nombre de «sums» (unions) et de «produits» (produits croisés) d’autres types.

    Maintenant, nous pouvons définir F-algèbre. F-algèbre n’est qu’une paire (T, f) , où T est un type et f est une fonction de type f :: FT -> T Dans nos exemples, les F-algèbres sont (IntList, Nil|Cons) et (IntTree, Leaf|Branch) . Notez cependant que malgré ce type de fonction, f est identique pour chaque F, T et f eux-mêmes peuvent être arbitraires. Par exemple, (Ssortingng, g :: 1 | (Int x Ssortingng) -> Ssortingng) ou (Double, h :: Int | (Double, Double) -> Double) pour certains g et h sont aussi des F-algèbres pour correspondant F.

    Ensuite, nous pouvons introduire des homomorphismes de l’algèbre F , puis des algèbres F initiales , qui ont des propriétés très utiles. En fait, (IntList, Nil|Cons) est une première algèbre F1 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 ils sont plus complexes et abstraits que nécessaire.

    Néanmoins, le fait que, disons, (IntList, Nil|Cons) soit F-algèbre nous permet de définir fold fonction de type fold sur ce type. Comme vous le savez, fold 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 la sum 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 tout type de données récursif.

    Ce qui suit est une signature de la fonction foldr :

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

    Notez que j’ai utilisé des accolades pour séparer les deux premiers arguments du dernier. Cette fonction n’est pas réelle, mais elle est isomorphe (c’est-à-dire que vous pouvez facilement obtenir les unes des autres et vice versa). Partiellement appliqué foldr aura la signature suivante:

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

    Nous pouvons voir que c’est une fonction qui prend une liste d’entiers et renvoie un entier unique. Définissons cette fonction en fonction de notre type IntList .

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

    Nous voyons que cette fonction est composée de deux parties: la première partie définit le comportement de cette fonction sur Nil partie d’ IntList et la deuxième partie définit le comportement de la fonction sur la partie Cons .

    Supposons maintenant que nous programmons non pas dans Haskell mais dans un langage permettant d’utiliser directement des types algébriques dans les signatures de type (enfin, techniquement, Haskell permet d’utiliser des types algébriques via tuples et Either ab , mais cela conduira à des verbosités inutiles). Considérons une fonction:

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

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

    IntList étant 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 r , qui convertit IntList en T , et cette fonction est unique. En effet, dans notre exemple, un catamorphisme pour sumFold est sumFold . Notez comment sumFold et sumFold sont similaires: ils ont presque la même structure! Dans la définition du reductor s , l’utilisation du paramètre (dont le type correspond à T ) correspond à l’utilisation du résultat du calcul de sumFold xs dans la définition de sumFold .

    Juste pour le rendre plus clair et vous aider à voir le modèle, voici un autre exemple, et nous recommençons à partir de la fonction de pliage qui en résulte. Considérons la fonction append 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] 

    C’est comme ça 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 .

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

    F-coalgearm

    F-coalgearm sont ce qu’on appelle le «double» terme pour F-algèbres. Ils nous permettent de définir les développements pour les types de données récursifs, c’est-à-dire un moyen de construire des structures récursives à partir d’une valeur donnée.

    Supposons que vous ayez le type suivant:

     data IntStream = Cons (Int, IntStream) 

    C’est un stream 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 correspondre les constructeurs de données, vous pouvez donc définir les fonctions suivantes sur IntStream :

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

    Vous pouvez naturellement “joindre” ces fonctions dans une fonction unique 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 type IntStream . Une chose similaire peut également être faite pour d’autres types de données récursives. Peut-être avez-vous déjà remarqué le modèle. Je parle d’une famille de fonctions de type

     g :: T -> FT 

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

     F1 T = Int × T 

    Maintenant, F-coalgebra est une paire (T, g) , où T est un type et g est une fonction de type g :: T -> FT . Par exemple, (IntStream, head&tail) est une F1-coalgebra. Encore une fois, tout comme dans les algèbres F, g et T peuvent être arbitraires, par exemple, (Ssortingng, h :: Ssortingng -> Int x Ssortingng) est également une F1-coalgebra pour certains h.

    Parmi tous les F-coalgearm, il existe ce que l’on appelle des coalges F-terminaux , qui sont doubles aux algèbres F initiales. Par exemple, IntStream est un terminal F-coalgebra. Cela signifie que pour tout type T et pour toute fonction p :: T -> F1 T il existe une fonction, appelée anamorphisme , qui convertit T en IntStream , et cette fonction est unique.

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

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

    natsBuilder :: Int -> F1 Int maintenant 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 similarité entre nats et natsBuilder . Il 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 stream d’applications successives de la fonction à la valeur:

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

    Sa fonction constructeur est la suivante:

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

    Alors iterate est un anamorphisme pour iterateBuilder .

    Conclusion

    Donc, en résumé, les algèbres F permettent de définir des plis, c’est-à-dire que les opérations qui réduisent la structure récursive en une seule valeur, et F-coalgearm permettent de faire le contraire: construire une structure infinie à partir d’une seule valeur.

    En fait, dans le Haskell, les algèbres de F et les coalges de F coïncident. C’est une très belle propriété qui est la conséquence de la présence de la valeur «bottom» dans chaque type. Ainsi, dans Haskell, les plis et les dépliements 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, alors je l’ai délibérément évité.

    J’espère que cela t’aides.

    Passer en revue le 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.

    Ci-dessous, une citation pour vous convaincre,

    En termes généraux, un programme dans certains langages de programmation manipule des données. Au cours du développement de l’informatique au cours des dernières décennies, il est devenu évident qu’une description abstraite 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. En outre, une telle abstrait facilite les preuves de correction.
    Ce désir a conduit à utiliser des méthodes algébriques en informatique, dans une twig appelée spécification algébrique ou théorie du type de données abstraite. Les objects d’étude sont des types de données en eux-mêmes, utilisant des notions de techniques familières à 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 révélées utiles pour saisir 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 insortingnsèquement dynamics intervenant en informatique. De telles structures impliquent généralement une notion d’état, qui peut être transformée de différentes manières. Les approches formelles de tels systèmes dynamics à base d’états utilisent généralement des automates ou des systèmes de transition, en tant que premières références classiques.
    Au cours de la dernière décennie, on a progressivement compris que ces systèmes basés sur l’état ne devaient pas être décrits comme des algèbres, mais comme des co-algèbres. Ce sont les doubles formels des algèbres, d’une manière qui sera précisée dans ce tutoriel. La double propriété de “l’initialité” pour les algèbres, à savoir la finalité, s’est révélée cruciale pour de telles co-algèbres. Et le principe de raisonnement logique nécessaire à ces co-algèbres 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. Comme catégories sont ce que l’on doit définir pour définir des foncteurs. (De plus, les foncteurs sont ce que l’on doit définir pour définir des transformations naturelles.)

    Qu’est-ce qu’un foncteur? C’est une transformation d’un ensemble à un autre qui conserve sa structure. (Pour plus de détails, il y a beaucoup de bonnes descriptions sur le net).

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

    Comment peut-il être lié à l’informatique? Le 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 est bon que l’exécution préserve la structure du programme. Ensuite, l’exécution peut être vue comme l’application d’un foncteur sur cet ensemble d’informations. (Celui qui définit le programme).

    Pourquoi F-co-algèbre? Le programme est double par essence car ils sont décrits par des informations et ils agissent en conséquence. Ensuite, les informations qui composent le programme et les modifient peuvent être vues de deux manières.

    • Données pouvant être définies comme les informations en cours de traitement par le programme.
    • Indiquez ce qui peut être défini comme les informations partagées par le programme.

    Alors, à ce stade, je voudrais dire que,

    • Algèbre F est l’étude de la transformation fonctorale agissant sur l’Univers de Data (tel que défini ici).
    • F-co-algearm est l’étude de la transformation fonctorale agissant sur l’univers de l’état (tel que défini ici).

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

    Je vais commencer par des choses qui sont évidemment liées à la programmation, puis append des éléments mathématiques pour les garder aussi concrets et concrets que possible.


    Citons quelques informaticiens sur la coinduction…

    http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html

    L’induction concerne les données finies, la co-induction concerne les données infinies.

    L’exemple typique de données infinies est le type d’une liste paresseuse (un stream). Par exemple, disons que l’object suivant est en mémoire:

      let (pi : int list) = (* some function which computes the digits of π. *) 

    L’ordinateur ne peut pas contenir tous les π, car sa mémoire est limitée! Mais ce qu’il peut faire, c’est tenir un programme fini, ce qui produira toute expansion arbitrairement longue de π que vous désirez. Tant que vous n’utilisez que des éléments finis de la liste, vous pouvez calculer avec cette liste infinie autant que vous le souhaitez.

    Cependant, considérez le programme suivant:

     let print_third_element (k : int list) = match k with | _ :: _ :: thd :: tl -> print thd print_third_element pi 

    Ce programme devrait imprimer le troisième chiffre de pi. Mais dans certains langages, tout argument d’une fonction est évalué avant d’être passé dans une fonction (ssortingct, pas paresseux, évaluation). Si nous utilisons cet ordre de réduction, notre programme ci-dessus s’exécutera pour toujours calculer les chiffres de pi avant de pouvoir être transmis à notre fonction imprimante (ce qui n’arrive jamais). Comme la machine n’a pas de mémoire infinie, le programme finira par manquer de mémoire et tomber en panne. Ce n’est peut-être pas le meilleur ordre d’évaluation.

    http://adam.chlipala.net/cpdt/html/Coinductive.html

    Dans les langages de programmation fonctionnels paresseux comme Haskell, les structures de données infinies sont partout. Des listes infinies et des types de données plus exotiques fournissent des abstractions pratiques pour la communication entre les parties d’un programme. Atteindre une commodité similaire sans structures paresseuses infinies nécessiterait, dans de nombreux cas, des inversions acrobatiques du stream de contrôle.

    http://www.alexandrasilva.org/#/talks.html exemples de coalgebras par Alexandra Silva


    Relier le contexte mathématique ambiant aux tâches de programmation habituelles

    Qu’est-ce qu’une “algèbre”?

    Les structures algébriques ressemblent généralement à:

    1. Des trucs
    2. Qu’est-ce que les choses peuvent faire

    Cela devrait sonner comme des objects avec 1. propriétés et 2. méthodes. Ou mieux encore, cela devrait ressembler à des signatures de type.

    Les exemples mathématiques standard incluent le monoïde ⊃ groupe ⊃ vecteur-espace ⊃ “une algèbre”. Les monoïdes sont comme des automates: séquences de verbes (par exemple, fghhnothing.fgf ). Un journal de bord qui ajoute toujours de l’historique et ne le supprime jamais serait un monoïde mais pas un groupe. Si vous ajoutez des inverses (par exemple des nombres négatifs, des fractions, des racines, en supprimant l’historique accumulé, en brisant un miroir brisé), vous obtenez un groupe.

    Les groupes contiennent des éléments pouvant être ajoutés ou soustraits ensemble. Par exemple, la Duration s peut être ajoutée. (Mais Date s ne le peut pas.) Les durées vivent dans un espace vectoriel (pas seulement un groupe) car elles peuvent également être mises à l’échelle par des nombres externes. (Une signature de type de scaling :: (Number,Duration) → Duration .)

    Les algèbres spaces les espaces vectoriels peuvent faire encore autre chose: il y a des m :: (T,T) → T Appelez cette “multiplication” ou non, car une fois que vous quittez les Integers il est moins évident de savoir ce que “multiplication” (ou “exponentiation” ) devrait être.

    (C’est pourquoi les gens recherchent des propriétés universelles (théoriques en catégories): leur dire ce que la multiplication devrait faire ou être :

    propriété universelle du produit )


    Algèbres → Coalgearm

    La multiplication est plus facile à définir que la multiplication, car pour aller de T → (T,T) il suffit de répéter le même élément. (“carte diagonale” – comme masortingces diagonales / opérateurs en théorie spectrale)

    Counit est généralement la trace (sum des entrées en diagonale), mais encore une fois, ce qui est important, c’est ce que votre pays fait ; trace est juste une bonne réponse pour les masortingces.

    La raison de regarder un espace double , en général, est qu’il est plus facile de penser dans cet espace. Par exemple, il est parfois plus facile de penser à un vecteur normal qu’au plan normal, mais vous pouvez contrôler des avions (y compris des hyperplans) avec des vecteurs (et je parle maintenant du vecteur géomésortingque familier, comme dans un traceur de rayons). .


    Apprivoiser (dés) les données structurées

    Les mathématiciens sont peut-être en train de modéliser quelque chose d’amusant comme les TQFT , alors que les programmeurs doivent lutter avec

    • dates / heures ( + :: (Date,Duration) → Date ),
    • lieux ( Paris(+48.8567,+2.3508) ! C’est une forme, pas un point.),
    • JSON non structuré qui est censé être cohérent dans un certain sens,
    • XML erroné mais proche,
    • des données SIG incroyablement complexes qui devraient satisfaire des charges de relations sensibles,
    • expressions régulières qui signifient quelque chose pour vous, mais signifient beaucoup moins de perl.
    • CRM qui devrait contenir tous les numéros de téléphone et tous les emplacements de villa du dirigeant, son nom et son prénom, son anniversaire et tous les cadeaux précédents, chacun devant satisfaire à des relations “évidentes” (évidentes pour le client). difficile à coder,
    • …..

    Les informaticiens, quand ils parlent de coalgearm, ont généralement en tête des opérations, comme les produits cartésiens. Je pense que c’est ce que les gens veulent dire quand ils disent comme “Les algèbres sont des houillères à Haskell”. Mais dans la mesure où les programmeurs doivent modéliser des types de données complexes comme le Place , la Date/Time et le Customer et faire en sorte que ces modèles ressemblent autant que possible au monde réel (ou du moins à la vision de l’utilisateur final) Je crois que les duels pourraient être utiles au-delà du seul monde.