Wie definiere ich eine Funktion induktiv für zwei Argumente in Coq?

14

Wie kann ich Coq davon überzeugen, dass die unten angegebene rekursive Funktion endet? Die Funktion akzeptiert zwei induktive Argumente. Intuitiv wird die Rekursion abgebrochen, weil eines der beiden Argumente zerlegt wird.

Insbesondere nimmt die Funktion zwei Bäume als Eingabe.

Inductive Tree :=
| Tip: Tree
| Bin: Tree -> Tree -> Tree.

Auf Bäumen mache ich gerne den folgenden Induktionsstil.

Inductive TreePair :=
| TipTip : TreePair
| TipBin : Tree -> Tree -> TreePair
| BinTip : Tree -> Tree -> TreePair
| BinBin : TreePair -> TreePair -> TreePair.

Fixpoint pair (l r: Tree): TreePair :=
  match l with
    | Tip =>
      match r with
        | Tip => TipTip
        | Bin rl rr => TipBin rl rr
      end
    | Bin ll lr =>
      match r with
        | Tip => BinTip ll lr
        | Bin rl rr => BinBin (pair l rl) (pair lr r)
      end
  end.

Die Definition von TreePair wird akzeptiert, aber die Definition des Funktionspaares liefert die Fehlermeldung:

Error: Cannot guess decreasing argument of fix.

Ich bin also daran interessiert, wie ich Coq von der Kündigung überzeugen kann.

yhirai
quelle
1
Haben Sie versucht, l und r als Produkt zu übergeben, anstatt Currys zu verwenden? Das sollte es weiter helfen.
Per Vognsen
1
Einige Leute denken, dass diese Frage über die Programmierung und außerhalb des Umfangs dieser Website ist. Ich bin mir zwar nicht sicher, ob ich damit einverstanden bin, aber Sie möchten vielleicht etwas über das potenzielle Problem erfahren. Wenn jemand etwas über die Angemessenheit zu sagen hat, schreibe bitte in die Metadiskussion, mit der ich verlinkt bin.
Tsuyoshi Ito
3
Bei dieser Frage geht es wirklich darum, monoton abnehmende Grenzen für Datenstrukturen pairfestzulegen , um sicherzustellen, dass die Operation genau definiert ist. Coq ist nur das Fahrzeug.
Dave Clarke

Antworten:

12

Die Fixpunktdefinitionen von Coq erfordern, dass induktive Anrufe ein strukturell kleineres Argument erhalten. Im Grunde genommen benötigt ein Fixpunktkonstrukt ein einziges Argument: Es gibt kein integriertes Konzept für eine rekursive Definition über zwei Argumente. Glücklicherweise enthält Coqs Definition von strukturell kleiner Typen höherer Ordnung, was äußerst leistungsfähig ist.

Ihre Fixpunktdefinition mit zwei Argumenten folgt einem einfachen Muster: Entweder wird das erste Argument kleiner, oder das erste Argument bleibt identisch, und das zweite Argument wird kleiner. Dieses recht häufige Muster kann durch ein einfaches Fix-in-Fix behandelt werden.

Fixpoint pair l := fix pair1 (r : Tree) :=
  match l with
    | Tip => match r with
              | Tip => TipTip
              | Bin rl rr => TipBin rl rr
            end
    | Bin ll lr => match r with
                    | Tip => BinTip ll lr
                    | Bin rl rr => BinBin (pair1 rl) (pair lr r)
                   end
  end.

In komplexeren Fällen oder wenn Ihr Geschmack so ist, können Sie eine Rekursion verwenden, die der in Mathematikkursen gelehrten näher kommt, indem Sie den Fixpunkt aus einer Schrittberechnung und einem separaten Begründungsargument aufbauen , wobei häufig ein ganzzahliges Maß verwendet wird . Sie können auch festlegen, dass Ihre Definition eher wie ein klassisches Programm in einer nicht vollständigen Sprache mit einer separaten Terminierung in der ProgramUmgangssprache aussieht .

Gilles 'SO - hör auf böse zu sein'
quelle
Jetzt weiß ich, dass ich darum gebeten habe!
Yhirai
Wird es einen Unterschied machen, wenn ich fix pair1 rin den zweiten Zweig der obersten Ebene schiebe match(und natürlich den ersten Zweig anpasse, um einen Funktionstyp entsprechend zurückzugeben)?
Tag
@plmday: In beide Richtungen arbeiten. Sie sind in Bezug auf eine angemessene Definition der Extensionalität weitgehend gleichwertig, und, was noch wichtiger ist, sie sind beide gut typisiert (das Umschreiben der Extensionalität ändert nichts an den relevanten Kovarianz- (Positivitäts-) Eigenschaften).
Gilles 'SO- hör auf böse zu sein'