Ne Hask ou Agda ont égaliseurs?

Question

J'ai été un peu indécis quant à savoir si c'était des mathématiques.SE question ou une DONC une, mais je soupçonne que les mathématiciens en général sont assez rare de savoir ou de soins de bien de cette catégorie en particulier, tandis que Haskell programmeurs pourraient bien le faire.

Donc, nous savons que Hask a produits, plus ou moins (je travaille avec idéalisée-Hask, ici, bien sûr). Je suis intéressé de savoir si ou non il a égaliseurs (dans ce cas, il aurait toutes les limites).

Intuitivement, il semble que non, puisque vous ne pouvez pas faire de séparation comme vous pouvez sur les ensembles, et ainsi de sous-objets semblent difficiles à reproduire en général. Mais pour un cas spécifique que vous souhaitez venir avec, il semble que vous seriez en mesure de le pirater de travail de l'égaliseur dans le Jeu et de comptage (car après tout, chaque Haskell type est dénombrable et tous ensemble dénombrable est isomorphe soit à un type fini ou le naturals, qui Haskell a). Donc je ne vois pas comment je voudrais trouver un contre-exemple.

Maintenant, Agda semble un peu plus prometteur: il est relativement facile de former des sous-objets. Évidemment, la sigma type Σ A (λ x → f x == g x) d'un égaliseur? Si les détails n'en sont pas, est-il moralement un égaliseur?

Answer 1

tl;dr le candidat proposé n'est pas tout à fait un égaliseur, mais sa pertinence homologue de l'

Le candidat à un égaliseur dans Agda semble bon. Donc, nous allons juste essayer. Nous allons avoir besoin de quelques kit de base. Voici mon refusenik ASCII dépendante de la paire type et homogène intensionnel de l'égalité.

record Sg (S : Set)(T : S -> Set) : Set where
  constructor _,_
  field
    fst : S
    snd : T fst
open Sg

data _==_ {X : Set}(x : X) : X -> Set where
  refl : x == x

Voici votre candidat pour un égaliseur pour deux fonctions

Q : {S T : Set}(f g : S -> T) -> Set
Q {S}{T} f g = Sg S \ s -> f s == g s

avec l' fst projection envoyant Q f g en S.

Ce qu'il dit: un élément de Q f g est un élément s du type de source, avec une preuve qu' f s == g s. Mais est-ce un égaliseur? Nous allons essayer de faire en sorte.

Pour vous dire que l'égaliseur est, je dois définir la fonction de la composition.

_o_ : {R S T : Set} -> (S -> T) -> (R -> S) -> R -> T
(f o g) x = f (g x)

Alors maintenant, j'ai besoin de prouver que l' h : R -> S qui identifie f o h et g o h doit facteur par le candidat fst : Q f g -> S. J'ai besoin à la fois d'offrir à l'autre composant, u : R -> Q f g et la preuve qu'en effet, h facteurs comme l' fst o u. Voici l'image: (Q f g , fst) est un égaliseur si à chaque fois que le diagramme commute sans u, il existe un unique façon d'ajouter de la u avec le diagramme encore les déplacements.

Ici va à l'existence de la médiation u.

mediator : {R S T : Set}(f g : S -> T)(h : R -> S) ->
           (q : (f o h) == (g o h)) ->
           Sg (R -> Q f g) \ u -> h == (fst o u)

Clairement, je doit choisir le même élément de la S que h choix.

mediator f g h q = (\ r -> (h r , ?0)) , ?1

me laissant avec deux obligations de preuve

?0 : f (h r) == g (h r)
?1 : h == (\ r -> h r)

Maintenant, ?1 peut-être juste refl comme Agda de la définition de l'égalité a l'eta-droit pour les fonctions. Pour ?0, nous sommes bénis en q. L'égalité des fonctions à l'égard de l'application

funq : {S T : Set}{f g : S -> T} -> f == g -> (s : S) -> f s == g s
funq refl s = refl

afin que nous puissions prendre en ?0 = funq q r.

Mais laissez-nous célébrons pas prématurément, l'existence d'une médiation morphism n'est pas suffisant. Nous avons besoin aussi de son unicité. Et ici, la roue est susceptible d'être bancale, car == est intensionnel, de sorte que l'unicité n'y a qu'une seule façon de mettre en œuvre la médiation de la carte. Mais alors, nos hypothèses sont également intensionnel...

Voici notre obligation de preuve. Nous devons montrer que toute autre médiation morphism est égale à celle choisie par l' mediator.

mediatorUnique :
  {R S T : Set}(f g : S -> T)(h : R -> S) ->
  (qh : (f o h) == (g o h)) ->
  (m : R -> Q f g) ->
  (qm : h == (fst o m)) ->
  m == fst (mediator f g h qh)

Nous pouvons immédiatement remplacer par qm et obtenir

mediatorUnique f g .(fst o m) qh m refl = ?

? :  m == (\ r -> (fst (m r) , funq qh r))

ce qui semble bon, parce que Agda a eta lois pour les enregistrements, nous savons que

m == (\ r -> (fst (m r) , snd (m r)))

mais quand nous essayons de faire en ? = refl, nous obtenons la plainte

snd (m _) != funq qh _ of type f (fst (m _)) == g (fst (m _))

ce qui est gênant, car l'identité des épreuves uniques (dans la configuration standard). Maintenant, vous pouvez sortir de ce en postulant la fusion et à l'aide de quelques autres faits au sujet de l'égalité

postulate ext : {S T : Set}{f g : S -> T} -> ((s : S) -> f s == g s) -> f == g

sndq : {S : Set}{T : S -> Set}{s : S}{t t' : T s} ->
       t == t' -> _==_ {Sg S T} (s , t) (s , t')
sndq refl = refl

uip : {X : Set}{x y : X}{q q' : x == y} -> q == q'
uip {q = refl}{q' = refl} = refl

? = ext (\ s -> sndq uip)

mais c'est exagéré, parce que le seul problème est l'ennuyeux égalité de preuve d'incompatibilité: la calculable parties de la mise en œuvre de match sur le nez. Donc la solution est de travailler avec des non-pertinence. - Je remplacer Sg par l' Existential quantificateur, dont le deuxième élément est marqué comme non pertinente d'un point. Maintenant, il n'importe pas qui la preuve que nous utilisons que le témoin est bon.

record Ex (S : Set)(T : S -> Set) : Set where
  constructor _,_
  field
    fst : S
    .snd : T fst
open Ex

et le nouveau candidat de l'égaliseur est

Q : {S T : Set}(f g : S -> T) -> Set
Q {S}{T} f g = Ex S \ s -> f s == g s

L'ensemble de la construction passe par comme avant, sauf que dans le dernier obligation

? = refl

sont acceptés!

Donc oui, même dans le intensionnel réglage, l'eta lois et la capacité de marquer des champs comme hors de propos nous donner des égaliseurs.

Pas de indécidable le typage a été impliqué dans cette construction.

Answer 2

Hask

Hask n'ont pas les égaliseurs. Une chose importante à retenir est que de penser à un type (ou les objets dans n'importe quelle catégorie) et de leurs classes d'isomorphisme vraiment la demande de la réflexion sur les flèches. Ce que vous dites sur le sous-jacent est vrai, mais avec des types de isomorphe ensembles sous-jacents ne sont certainement pas nécessairement isomorphe. Une différence entre Hask et que Hask flèches doivent être calculable, et en fait pour idéalisée Hask, ils doivent être total.

J'ai passé tout en essayant de trouver un véritable défendable contre-exemple, et a trouvé quelques références à croire qu'il ne peut pas être fait, mais sans preuves. Cependant, j'ai quelques "moral" contre-exemples si vous voulez, je ne peux pas prouver qu'aucun égaliseur existe en Haskell, mais il semble bien impossible!

Exemple 1

f, g: ([Int], Int) -> Int

f (p,v) = treat p as a polynomial with given coefficients, and evaluate p(v).
g _ = 0

L'égaliseur "devrait" être le type de tous les couples (p,n) où p(n) = 0, avec une fonction d'injection de ces paires dans ([Int], Int). Par Hilbert 10e problème, cet ensemble est indécidable. Il me semble que ce devrait exclure la possibilité d'une Haskell type, mais je ne peux pas prouver que (est-il possible qu'il y a une étrange façon de construire ce type que personne n'a découvert?). Il peut-être que je n'ai pas connecté à un point ou deux, peut-être prouver que c'est impossible n'est-ce pas difficile?

Exemple 2

Disons que vous avez une programmation de langue. Vous avez un compilateur qui prend le code source et une entrée et produit une fonction, pour laquelle le point fixe de la fonction est la sortie. (Alors que nous n'avons pas les compilateurs de ce genre, la spécification de la sémantique un peu comme ce n'est pas rare). Donc, vous avez

compiler : String -> Int -> (Int -> Int)

(Onu)curry que dans une fonction

compiler' : (String, Int, Int) -> Int

et ajouter une fonction

id' : (String, Int, Int) -> Int
id' (_,_,x) = x

Ensuite, l'égaliseur de compilateur',' id serait la collection de triplets de la source de programme, d'entrée, de sortie, et c'est uncomputable parce que la programmation de la langue est pleinement général.

D'Autres Exemples

Choisissez votre favori problème indécidable: il consiste généralement à déterminer si un objet est le membre d'un ensemble. Vous avez souvent un total fonction qui peut être utilisée pour vérifier cette propriété pour un objet particulier. Vous pouvez utiliser cette fonction pour créer un égaliseur où le type doit être de tous les articles dans votre indécidable ensemble. C'est là que les deux premiers exemples est venu, et il y a des tonnes de plus.

Agda

Je ne suis pas aussi familier avec Agda. Mon intuition est que votre sigma-type doit être un égaliseur: vous pouvez écrire le type, avec le nécessaire, l'injection de la fonction, et on dirait qu'il répond à la définition entièrement. Toutefois, comme quelqu'un qui n'utilise pas Agda, je ne pense pas que je suis vraiment qualifié pour vérifier les détails.

La vraie question pratique, c'est que le typage que sigma type ne sera pas toujours calculable, donc il n'est pas toujours utile de le faire. Dans tous les exemples ci-dessus, vous pouvez écrire le Sigma type que vous avez fourni, mais vous ne serez pas en mesure de facilement vérifier si quelque chose est un membre de ce type sans preuve.

D'ailleurs, c'est pourquoi Haskell ne devrait pas être en mesure d'avoir des égaliseurs: si il l'a fait, la vérification de type serait indécidable! Types de charge est ce qui fait tout de tiques. Ils devraient être en mesure d'exprimer intéressant structures mathématiques dans ses types, tout en Haskell peut pas depuis sa typesystem est decideable. Je souhaite donc naturellement s'attendre à idéalisée Agda d'avoir toutes les limites (je serais déçu sinon). Il en va de même pour les autres dépendante tapé langues; Coq, par exemple, devrait certainement avoir toutes les limites.