Ist die Reihenfolge der Deklarationen in einem induktiven Typ von Bedeutung?

9

Ich habe mich gefragt, ob die Reihenfolge der induktiven Deklarationen von Bedeutung sein kann.

In Coq können Sie beispielsweise Folgendes definieren Nat:

Inductive Nat :=
  | O : Nat
  | S : Nat -> Nat.

oder

Inductive Nat :=
  | S : Nat -> Nat
  | O : Nat.

Dies wird möglicherweise die Reihenfolge der Parameter im automatisch generierten Eliminator ändern, aber das ist keine große Sache.

Ich frage mich, ob es möglich ist, eine Erklärung wie zu schreiben

Inductive typewhereordermatters :=
  | cons1 : type1
  | cons2 : type2.

Wo type2ist ein abhängiger Typ, abhängig von cons1? (und in diesem Fall hätte das Schreiben der Erklärungen in der anderen Reihenfolge keine Bedeutung, da type2sich darauf beziehen würde, cons1welche noch nicht existiert).

lo.logic type-theory coq dependent-type Guillaume Brunerie
quelle

Antworten:

10

  1. Die Reihenfolge spielt keine Rolle. Ich kann mir keinen Fall vorstellen, in dem es so wäre. Wie Andrej Bauer in einem Kommentar betont, ist das Ergebnis kanonisch isomorph zum Original , wenn Sie die Reihenfolge ändern .

  2. Ein Fall kann nicht von einem anderen Fall abhängen. Die Elemente der Summe stellen eine Wahl dar, daher ist es nicht sinnvoll, dass die getroffene Wahl von einer Wahl abhängt, die nicht getroffen wird.

Dave Clarke
quelle
2
Sie können Ihren ersten Punkt genauer beschreiben. Die Reihenfolge spielt keine Rolle. Wenn Sie die Reihenfolge ändern, ist das Ergebnis kanonisch isomorph zum Original.
Andrej Bauer
2
@ Dave: Danke! Ich habe diese Frage wegen (der hochexperimentellen Theorie) höherer induktiver Typen gestellt, bei denen dieses Phänomen aufzutreten scheint , und ich wollte wissen, ob dies auch bei regulären induktiven Typen der Fall sein kann.
Guillaume Brunerie
1
@ Guillaume: Ich bin mir nicht sicher, auf welches Phänomen Sie mit dem Link hinweisen. Die verschiedenen Konstruktorklauseln einer Datentypdefinition können nicht voneinander abhängen, unabhängig davon, ob es sich um einen Datentyp höherer Ordnung handelt oder nicht. Vielleicht denken Sie an abhängige Datensätze (die unter dem Link verwendet werden und in Agda und Coq verfügbar sind )?
Noam Zeilberger
1
@Noam: Im Beispiel des höherinduktiven circleTyps loophängt der Typ des Konstruktors vom baseKonstruktor ab.
Guillaume Brunerie
2
@ Guillaume: Ich sehe jetzt (sie führen eine experimentelle Syntax ein), weiß nicht, wie ich das verpasst habe.
Noam Zeilberger
6

Ist die Bestellung wichtig, wie Sie fragen? Nein.

Aber ist die Reihenfolge für die Funktionsweise des Proof-Assistenten völlig irrelevant? Wieder nein. In Matita, ein Beweis Assistenten sehr ähnlich Coq, in dem die Reihenfolge Bauer in einer induktiven Definition geschrieben tut Angelegenheit für die Typprüfung, speziell wenn Art einer Übereinstimmung Ausdruck zu überprüfen.

Matita muss zuerst überprüfen, ob alle Konstruktoren im Hauptteil des Spiels abgeglichen werden. Dazu werden die Konstruktoren in der Reihenfolge durchlaufen, in der sie deklariert sind. Dann muss der eigentliche Übereinstimmungsausdruck in umgekehrter Reihenfolge überprüft werden, wobei zuerst der Fall für den zuletzt deklarierten Konstruktor überprüft wird. Dieser Typ wird dann ausgeführt und verwendet, um die anderen Fälle zu überprüfen.

Dies wird sehr oft beim Schreiben eines großen Übereinstimmungsausdrucks angezeigt. Sie möchten zuerst die einfachen Fälle ausfüllen und schwierigere Fälle unter einem Platzhalter belassen. Überprüfen Sie regelmäßig, was Sie geschrieben haben, um sicherzustellen, dass es sinnvoll ist. Manchmal kann Matita den Typ des unvollständigen Übereinstimmungsausdrucks nicht ableiten, tut dies jedoch recht gerne, wenn Sie den Fall für den letzten im induktiven Typ definierten Konstruktor ausfüllen.

Ich nehme an, obwohl ich nicht sicher bin, dass Coq etwas Ähnliches tut.

Dominic Mulligan
quelle