J'ai entendu le terme "coalgebras" à plusieurs reprises dans la programmation fonctionnelle et les cercles PLT, en particulier lorsque la discussion porte sur des objets, des comonades, des lentilles, etc. Googler ce terme donne des pages qui donnent une description mathématique de ces structures qui est à peu près incompréhensible pour moi. Quelqu'un peut-il expliquer ce que les coalgebras signifient dans le contexte de la programmation, quelle est leur signification et comment ils se rapportent aux objets et aux comonades?
scala
haskell
functional-programming
category-theory
recursion-schemes
missingfaktor
la source
la source
Réponses:
Algèbres
Je pense que le point de départ serait de comprendre l'idée d'une algèbre . Ce n'est qu'une généralisation des structures algébriques comme les groupes, les anneaux, les monoides et ainsi de suite. La plupart du temps, ces choses sont introduites en termes d'ensembles, mais comme nous sommes entre amis, je parlerai plutôt des types Haskell. (Je ne peux pas résister à utiliser des lettres grecques, elles rendent tout plus cool!)
Une algèbre n'est donc qu'un type
τ
avec quelques fonctions et identités. Ces fonctions prennent des nombres différents d'arguments de typeτ
et produisent unτ
: non-curry, ils ressemblent tous(τ, τ,…, τ) → τ
. Ils peuvent également avoir des «identités» - des élémentsτ
qui ont un comportement spécial avec certaines des fonctions.L'exemple le plus simple est le monoïde. Un monoïde est tout type
τ
ayant une fonctionmappend ∷ (τ, τ) → τ
et une identitémzero ∷ τ
. D'autres exemples incluent des choses comme des groupes (qui sont comme des monoïdes sauf avec uneinvert ∷ τ → τ
fonction supplémentaire ), des anneaux, des réseaux et ainsi de suite.Toutes les fonctions fonctionnent
τ
mais peuvent avoir des arités différentes. Nous pouvons les écrire commeτⁿ → τ
, oùτⁿ
correspond à un tuple den
τ
. De cette façon, il est logique de penser aux identités commeτ⁰ → τ
où seτ⁰
trouve 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é «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 réseaux et ainsi de suite susmentionnés - suivent tous un modèle similaire, alors ils l'ont résumé. L'avantage de faire cela est le même qu'en programmation: il crée des preuves réutilisables et facilite certains types de raisonnement.
Algèbres F
Cependant, nous n'avons pas tout à fait fini avec l'affacturage. Jusqu'à présent, nous avons un tas de fonctions
τⁿ → τ
. Nous pouvons réellement faire une astuce pour les combiner tous en une seule fonction. En particulier, regardons les monoïdes: nous avonsmappend ∷ (τ, τ) → τ
etmempty ∷ () → τ
. Nous pouvons les transformer en une seule fonction en utilisant un type de somme—Either
. Cela ressemblerait à ceci:Nous pouvons réellement utiliser cette transformation à plusieurs reprises pour combiner toutes les
τⁿ → τ
fonctions en une seule, pour n'importe quelle algèbre. (En fait, nous pouvons le faire pour n'importe quel nombre de fonctionsa → τ
,b → τ
et ainsi de suite pour toutesa, b,…
.)Cela nous permet de parler des algèbres en tant que type
τ
avec une seule fonction d'un certain désordre deEither
s à un seulτ
. Pour monoids, ce gâchis est:Either (τ, τ) ()
; pour les groupes (qui ont un supplément deτ → τ
fonctionnement), il 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 que ce ne sont que 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 τ:Nous pouvons faire la même chose pour les groupes et les anneaux et les réseaux et toutes les autres structures possibles.
Quoi d'autre est spécial sur tous ces types? Eh bien, ils sont tous
Functors
! Par exemple:Nous pouvons donc généraliser encore plus notre idée d'une algèbre. C'est juste un type
τ
avec une fonctionf τ → τ
pour un foncteurf
. En fait, nous pourrions l'écrire sous forme de classe:Ceci est souvent appelé «algèbre F» car il est déterminé par le foncteur
F
. Si nous pouvions appliquer partiellement des classes de caractères, nous pourrions définir quelque chose commeclass Monoid = Algebra MonoidArgument
.Coalgebras
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'un F-coalgebra? Eh bien, le co implique que c'est le "double" d'une algèbre, c'est-à-dire que nous prenons une algèbre et retournons quelques flèches. Je ne vois qu'une seule flèche dans la définition ci-dessus, donc je vais juste inverser cela:
Et c'est tout! Maintenant, cette conclusion peut sembler un peu désinvolte (hé). Il vous dit ce qu'est un charbon, mais ne donne pas vraiment un aperçu de son utilité ou pourquoi nous nous en soucions. J'y reviendrai dans un instant, une fois que je trouverai ou trouverai un bon exemple ou deux: 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 houilleC
qui spécifie les méthodes et les propriétés des objets.Comme le montre l'exemple d'algèbre, si nous avons un tas de fonctions comme
a → τ
etb → τ
pour n'importe laquellea, b,…
, nous pouvons les combiner toutes en une seule fonction en utilisantEither
, un type de somme. La double «notion» consisterait à combiner un tas de fonctions de typeτ → a
,τ → b
et ainsi de suite. Nous pouvons le faire en utilisant le double d'un type de somme - un type de produit. Donc, étant donné les deux fonctions ci-dessus (appeléesf
etg
), nous pouvons en créer une seule comme ceci:Le type
(a, a)
est un foncteur au sens simple du terme, il correspond donc certainement à notre notion de F-coalgebra. Cette astuce particulière nous permet de regrouper un tas de fonctions différentes - ou, pour la POO, les méthodes - en une seule fonction de typeτ → f τ
.Les éléments de notre type
C
représentent l' état interne de l'objet. Si l'objet a des propriétés lisibles, elles doivent pouvoir dépendre de l'état. La façon la plus évidente de le faire est d'en faire une fonctionC
. Donc, si nous voulons une propriété de longueur (par exempleobject.length
), nous aurions une fonctionC → Int
.Nous voulons des méthodes qui peuvent prendre un argument et modifier l'état. Pour ce faire, nous devons prendre tous les arguments et en produire un nouveau
C
. Imaginons unesetPosition
méthode qui prend unex
ety
coordonnée:object.setPosition(1, 2)
. Il ressemblerait à ceci:C → ((Int, Int) → C)
.Le motif important ici est que les "méthodes" et les "propriétés" de l'objet prennent l'objet lui-même comme premier argument. C'est exactement comme le
self
paramètre en Python et comme l'implicitethis
de nombreux autres langages. Un cogèbre essentiellement encapsule tout le comportement de prendre unself
paramètre: c'est ce que le premierC
enC → F C
est.Alors mettons tout cela ensemble. Imaginons une classe avec une
position
propriété, unename
propriété et unesetPosition
fonction:Nous avons besoin de deux parties pour représenter cette classe. Premièrement, nous devons représenter l'état interne de l'objet; dans ce cas, il contient juste deux
Int
s et unString
. (C'est notre typeC
.) Ensuite, nous devons trouver le charbon de bois représentant la classe.Nous avons deux propriétés à écrire. Ils sont assez banals:
Il nous suffit maintenant de pouvoir mettre à jour la position:
C'est comme une classe Python avec ses
self
variables explicites . Maintenant que nous avons un tas deself →
fonctions, nous devons les combiner en une seule fonction pour la houille. Nous pouvons le faire avec un simple tuple:Le type
((Int, Int), String, (Int, Int) → c)
-pour toutc
-est un foncteur, donccoop
a le forme que nous voulons:Functor f ⇒ C → f C
.Compte tenu de cela,
C
ainsi que decoop
former une houillère 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 illimité de méthodes et de propriétés pour nos objets.Cela nous permet d'utiliser le raisonnement coalgebrique pour traiter les classes. Par exemple, nous pouvons introduire la notion d '"homomorphisme de F-coalgebra" pour représenter les transformations entre classes. C'est un terme qui fait peur et qui signifie simplement une transformation entre les houillères qui préserve la structure. Cela facilite beaucoup la réflexion sur le mappage de classes sur d'autres classes.
En bref, un F-coalgebra représente une classe en ayant un tas de propriétés et de méthodes qui dépendent toutes d'un
self
paramètre contenant l'état interne de chaque objet.Autres catégories
Jusqu'à présent, nous avons parlé des algèbres et des houillères en tant que types Haskell. Une algèbre n'est qu'un type
τ
avec une fonctionf τ → τ
et une houille 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 une certaine catégorie
C
. Premièrement, nous avons besoin d'un foncteur,F : C → C
c'est-à-dire d'un endofoncteur . (Tous les HaskellFunctor
sont en fait des endofoncteurs deHask → Hask
.) Ensuite, une algèbre n'est qu'un objetA
deC
morphismeF A → A
. Une houille est la même sauf avecA → F A
.Qu'avons-nous à gagner en considérant d'autres catégories? Eh bien, nous pouvons utiliser les mêmes idées dans différents contextes. Comme des monades. À Haskell, une monade est un type
M ∷ ★ → ★
avec trois opérations:La
map
fonction n'est qu'une preuve du fait qu'ilM
s'agit d'unFunctor
. On peut donc dire qu'une monade n'est qu'un foncteur avec deux opérations:return
etjoin
.Les foncteurs forment eux-mêmes une catégorie, 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 bel article aidant à expliquer l'idée. Il en parle
concat
, qui nejoin
concerne que les listes.Avec les foncteurs Haskell, la composition de deux foncteurs est un foncteur lui-même. En pseudocode, nous pourrions écrire ceci:
Cela nous aide à penser
join
comme un mappage à partir def ∘ f → f
. Le type dejoin
est∀α. f (f α) → f α
. Intuitivement, nous pouvons voir comment une fonction valable pour tous les typesα
peut être considérée comme une transformation def
.return
est une transformation similaire. Son type est∀α. α → f α
. Cela semble différent - le premierα
n'est pas "dans" un foncteur! Heureusement, nous pouvons résoudre ce problème en ajoutant un foncteur là d'identité:∀α. Identity α → f α
. Il enreturn
va de même pour une transformationIdentity → f
.Maintenant, nous pouvons considérer une monade comme une simple algèbre basée sur un foncteur
f
avec des opérationsf ∘ f → f
etIdentity → f
. Cela ne vous semble-t-il pas familier? Il est très similaire à un monoïde, qui n'était qu'un typeτ
avec des opérationsτ × τ → τ
et() → τ
.Une monade est donc comme un monoïde, sauf qu'au lieu d'avoir un type, nous avons un foncteur. C'est le même type d'algèbre, juste dans une catégorie différente. (C'est là que l'expression "une monade n'est qu'un monoïde dans la catégorie des endofoncteurs" vient pour autant que je sache.)
Maintenant, nous avons ces deux opérations:
f ∘ f → f
etIdentity → f
. Pour obtenir la coalgebra correspondante, il suffit de retourner les flèches. Cela nous donne deux nouvelles opérations:f → f ∘ f
etf → Identity
. Nous pouvons les transformer en types Haskell en ajoutant des variables de type comme ci-dessus, en nous donnant∀α. f α → f (f α)
et∀α. f α → α
. Cela ressemble à la définition d'une comonade:Ainsi , un comonad est alors un cogèbre dans une catégorie de endofunctors.
la source
(,)
et le foncteur d'identité à()
. Un objet monoïde dans une catégorie monoïdale est un objet avec des flèches correspondant à votre algèbre monoïde, qui décrit un objet monoïde dans Hask avec des types de produits comme structure monoïdale. Un objet monoïde dans la catégorie des endofoncteurs sur C est une monade sur C, donc oui, votre compréhension est correcte. :]Les algèbres F et les algèbres F sont des structures mathématiques qui contribuent au raisonnement sur les types inductifs (ou récursifs ).
Algèbres F
Nous allons commencer par les algèbres F. J'essaierai 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:
Il est évident qu'il est récursif - en effet, sa définition se réfère à lui-même. Sa définition se compose de deux constructeurs de données, qui ont les types suivants:
Notez que j'ai écrit le type de
Nil
as() -> IntList
, pas simplementIntList
. Ce sont en fait des types équivalents du point de vue théorique, car le()
type n'a qu'un seul habitant.Si nous écrivons des signatures de ces fonctions d'une manière plus théorique, nous obtiendrons
où
1
est un ensemble d'unités (ensemble avec un élément) et l'A × B
opération est un produit croisé de deux ensemblesA
etB
(c'est-à-dire un ensemble de paires(a, b)
oùa
passe par tous les éléments deA
etb
passe par tous les éléments deB
).Union disjointe de deux ensembles
A
etB
est un ensembleA | 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 des deuxA
etB
, mais avec chacun de ces éléments `` marqués '' comme appartenant à l'unA
ou à l'autreB
, donc lorsque nous choisirons un élément de,A | B
nous saurons immédiatement si cet élément est venu deA
ou deB
.Nous pouvons «joindre»
Nil
etCons
fonctionner, afin qu'ils forment une seule fonction travaillant sur un ensemble1 | (Int × IntList)
:En effet, si la
Nil|Cons
fonction est appliquée à la()
valeur (qui, évidemment, appartient à1 | (Int × IntList)
set), alors elle se comporte comme si elle l'étaitNil
; siNil|Cons
est appliqué à n'importe quelle valeur de type(Int, IntList)
(ces valeurs sont également dans l'ensemble1 | (Int × IntList)
, il se comporte commeCons
.Considérons maintenant un autre type de données:
Il a les constructeurs suivants:
qui peut également être réunie en une seule fonction:
On peut voir que ces deux
joined
fonctions ont un type similaire: elles ressemblent toutes les deuxoù
F
est une sorte de transformation qui prend notre type et donne un type plus complexe, qui se compose dex
et d'|
opérations, d'usagesT
et éventuellement d'autres types. Par exemple, pourIntList
etIntTree
F
ressemble à ceci:Nous pouvons immédiatement remarquer que tout type algébrique peut être écrit de cette façon. En effet, c'est pourquoi ils sont appelés «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 l'algèbre F. L'algèbre F est juste une paire
(T, f)
, oùT
est un type etf
est une fonction de typef :: F T -> T
. Dans nos exemples, les algèbres F sont(IntList, Nil|Cons)
et(IntTree, Leaf|Branch)
. Notez, cependant, que malgré ce type def
fonction est le même pour chaque F,T
etf
eux - mêmes peuvent être arbitraires. Par exemple,(String, g :: 1 | (Int x String) -> String)
ou(Double, h :: Int | (Double, Double) -> Double)
pour certainsg
eth
sont également des algèbres F pour le F. correspondantEnsuite, nous pouvons introduire des homomorphismes d'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 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 ils sont plus complexes et abstraits que nécessaire.Néanmoins, le fait que, disons,
(IntList, Nil|Cons)
est l'algèbre F nous permet de définir unefold
fonction semblable à celle de 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 replier une liste d'entiers en une seule valeur qui est une somme de tous les éléments de la liste: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:Notez que j'ai utilisé des accolades pour séparer les deux premiers arguments du dernier. Ce n'est pas une
foldr
fonction réelle , mais elle lui est isomorphe (c'est-à-dire que vous pouvez facilement obtenir l'une de l'autre et vice versa). Partiellement appliquéfoldr
aura la signature suivante:Nous pouvons voir que c'est une fonction qui prend une liste d'entiers et retourne un seul entier. Définissons une telle fonction en termes de notre
IntList
type.Nous voyons que cette fonction se compose de deux parties: la première partie définit le comportement de cette fonction en
Nil
partieIntList
, et la seconde partie définit le comportement de la fonction enCons
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 (enfin, techniquement Haskell permet l'utilisation de types algébriques via des tuples et des
Either a b
types de données, mais cela conduira à une verbosité inutile). Considérons une fonction:On peut voir que
reductor
c'est une fonction de typeF1 Int -> Int
, tout comme dans la définition de l'algèbre F! En effet, la paire(Int, reductor)
est une algèbre F1.Parce qu'il
IntList
s'agit d'une algèbre F1 initiale, pour chaque typeT
et pour chaque fonction,r :: F1 T -> T
il existe une fonction, appelée catamorphisme pourr
, qui se convertitIntList
enT
, et cette fonction est unique. En effet, dans notre exemple un catamorphisme pourreductor
estsumFold
. Notez commentreductor
etsumFold
sont similaires: ils ont presque la même structure! L' utilisation en paramètre dereductor
définitions
(dont le type correspond àT
) correspond à l'utilisation du résultat du calcul desumFold xs
ensumFold
définition.Juste pour le rendre plus clair et vous aider à voir le motif, voici un autre exemple, et nous recommençons à partir de la fonction de pliage résultante. Considérons la
append
fonction qui ajoute son premier argument au second:Voici à quoi cela ressemble sur notre
IntList
:Encore une fois, essayons d'écrire le réducteur:
appendFold
est un catamorphisme pourappendReductor
lequel se transformeIntList
enIntList
.Donc, essentiellement, les algèbres F nous permettent de définir des «replis» sur des infrastructures de données récursives, c'est-à-dire des opérations qui réduisent nos structures à une certaine valeur.
F-coalgebras
Les algèbres F sont des termes dits «doubles» pour les algèbres F. Ils nous permettent de définir
unfolds
pour les types de données récursifs, c'est-à-dire un moyen de construire des structures récursives à partir d'une certaine valeur.Supposons que vous ayez le type suivant:
Il s'agit d'un flux infini d'entiers. Son seul constructeur a le type suivant:
Ou, en termes d'ensembles
Haskell vous permet de faire correspondre les modèles sur les constructeurs de données, vous pouvez donc définir les fonctions suivantes en travaillant sur
IntStream
s:Vous pouvez naturellement «joindre» ces fonctions en une seule fonction de type
IntStream -> Int × IntStream
:Remarquez comment le résultat de la fonction coïncide avec la représentation algébrique de notre
IntStream
type. Une opération similaire peut également être effectuée pour d'autres types de données récursives. Vous avez peut-être déjà remarqué le motif. Je fais référence à une famille de fonctions de typeoù
T
est un type. Désormais nous définironsMaintenant, F-coalgebra est une paire
(T, g)
, oùT
est un type etg
est une fonction de typeg :: T -> F T
. Par exemple,(IntStream, head&tail)
est un charbon-F1. Encore une fois, tout comme dans les algèbres F,g
etT
peut être arbitraire, par exemple,(String, h :: String -> Int x String)
est également un charbon-F1 pour quelque h.Parmi tous les coalgebras F, il existe des soi-disant F-coalgebras terminaux , qui sont duaux des algèbres F initiales. Par exemple,
IntStream
est un terminal F-coalgebra. Cela signifie que pour chaque typeT
et pour chaque fonction,p :: T -> F1 T
il existe une fonction, appelée anamorphisme , qui se transformeT
enIntStream
, et cette fonction est unique.Considérons la fonction suivante, qui génère un flux d'entiers successifs à partir de celui donné:
Inspectons maintenant une fonction
natsBuilder :: Int -> F1 Int
, c'est-à-direnatsBuilder :: Int -> Int × Int
:Encore une fois, nous pouvons voir une certaine similitude entre
nats
etnatsBuilder
. Il est très similaire à la connexion que nous avons observée précédemment avec les réducteurs et les plis.nats
est un anamorphisme pournatsBuilder
.Autre exemple, une fonction qui prend une valeur et une fonction et renvoie un flux d'applications successives de la fonction à la valeur:
Sa fonction de générateur est la suivante:
C'est alors
iterate
un anamorphisme pouriterateBuilder
.Conclusion
Donc, en bref, les algèbres F permettent de définir des plis, c'est-à-dire des opérations qui réduisent la structure récursive en une seule valeur, et les algèbres F permettent de faire le contraire: construire une structure [potentiellement] infinie à partir d'une seule valeur.
En fait, dans Haskell, les F-algèbres et les F-coalgebras coïncident. Il s'agit d'une très belle propriété qui est une conséquence de la présence de la valeur «bas» dans chaque type. Ainsi, dans Haskell, les plis et les dépliages 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 t'aides.
la source
appendReductor
semble un peu étrange et ne m'a pas vraiment aidé à voir le modèle là-bas ... :) Pouvez-vous vérifier qu'il est correct? .. À quoi devraient ressembler les types de réducteurs en général? Dans la définition der
là, estF1
déterminé par l'IntList, ou est-ce un F arbitraire?Passer en revue le didacticiel Un didacticiel sur les (co) algèbres et (co) induction devrait vous donner un aperçu de la co-algèbre en informatique.
En voici une citation pour vous convaincre,
Prélude, sur la théorie des catégories. La théorie des catégories devrait être renommée théorie des foncteurs. Les catégories sont ce que l'on doit définir pour définir les foncteurs. (De plus, les foncteurs sont ce qu'il faut définir pour définir les transformations naturelles.)
Qu'est-ce qu'un foncteur? C'est une transformation d'un ensemble à un autre qui préserve leur 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 semble bon que l'exécution conserve la structure du programme. L'exécution peut alors être vue comme l'application d'un foncteur sur cet ensemble d'informations. (Celui définissant le programme).
Pourquoi F-co-algèbre? Les programmes sont par essence duels car ils sont décrits par des informations et ils agissent en conséquence. Ensuite, principalement les informations qui composent le programme et les font changer peuvent être visualisées de deux manières.
À ce stade, je voudrais dire que,
Pendant la durée de vie d'un programme, les données et l'état coexistent et se complètent. Ils sont doubles.
la source
Je vais commencer par des trucs qui sont évidemment liés à la programmation, puis ajouter quelques trucs mathématiques, pour les garder aussi concrets et terre-à-terre que possible.
Citons quelques informaticiens sur la coinduction…
http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html
http://adam.chlipala.net/cpdt/html/Coinductive.html
http://www.alexandrasilva.org/#/talks.html
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 à:
Cela devrait ressembler à des objets avec 1. propriétés et 2. méthodes. Ou encore mieux, cela devrait ressembler à des signatures de type.
Les exemples mathématiques standard incluent monoïde ⊃ groupe ⊃ espace vectoriel ⊃ "une algèbre". Les monoïdes sont comme des automates: des séquences de verbes (par exemple,
f.g.h.h.nothing.f.g.f
). Ungit
journal qui ajoute toujours 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, la suppression de l'historique accumulé, la destruction d'un miroir brisé), vous obtenez un groupe.Les groupes contiennent des éléments qui peuvent être ajoutés ou soustraits ensemble. Par exemple, les
Duration
s peuvent être ajoutés ensemble. (Mais ceDate
n'est pas le cas.) Les durées vivent dans un espace vectoriel (pas seulement un groupe) car elles peuvent également être mises à l'échelle par des nombres extérieurs. (Une signature de type descaling :: (Number,Duration) → Duration
.)Les algèbres ⊂ les espaces vectoriels peuvent faire encore autre chose: il y en a
m :: (T,T) → T
. Appelez cela "multiplication" ou pas, car une fois que vous partez,Integers
il est moins évident de savoir ce que devrait être la "multiplication" (ou "exponentiation" ).(C'est pourquoi les gens se tournent vers les propriétés universelles (théoriques des catégories): pour leur dire ce que la multiplication devrait faire ou être :
)
Algèbres → Coalgebras
La comultiplication est plus facile à définir d'une manière qui ne semble pas arbitraire, que la multiplication, car pour partir de là,
T → (T,T)
il suffit de répéter le même élément. ("carte diagonale" - comme les matrices / opérateurs diagonaux dans la théorie spectrale)Counité est généralement la trace (somme des entrées en diagonale), bien qu'encore une fois ce qui est important est ce que votre counité fait ;
trace
est juste une bonne réponse pour les matrices.La raison de regarder un double espace , en général, est parce 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 auquel il est normal, mais vous pouvez contrôler les avions (y compris les hyperplans) avec des vecteurs (et maintenant je parle du vecteur géométrique familier, comme dans un traceur de rayons) .
Apprivoiser des données (non) structurées
Les mathématiciens peuvent modéliser quelque chose d'amusant comme celui de TQFT , tandis que les programmeurs doivent lutter avec
+ :: (Date,Duration) → Date
),Paris
≠(+48.8567,+2.3508)
! C'est une forme, pas un point.),Les informaticiens, lorsqu'ils parlent de houillères, ont généralement à l'esprit des opérations de configuration, comme les produits cartésiens. Je crois que c'est ce que les gens veulent dire quand ils disent "Les algèbres sont des houillères à Haskell". Mais dans la mesure où les programmeurs doivent modéliser complexes des types de données comme
Place
,Date/Time
etCustomer
-et font ces modèles ressemblent autant le monde réel (ou du moins vue de l'utilisateur final du monde réel) que possible, je crois duales, pourrait être utile au-delà du seul monde défini.la source