Frage Datenstrukturen mit nichtdeterministischen Komponenten in Coq


Ich versuchte, eine weniger naive monadische Kodierung von Nicht-Determinismus (weniger naiv als MonadPlus und allgemeine Listen) in Coq zu modellieren, die oft in Haskell verwendet wird; zum Beispiel sieht die Kodierung für Listen so aus

data List m a = Nil | Cons (m a) (m (List m a))

während die entsprechende Definition in Coq wie folgt aussehen möchte.

Inductive List (M: Type -> Type) (A: Type) :=
   Nil: List M A
 | Cons : M A -> M (List M A) -> List M A.

Diese Art der Definition ist jedoch in Coq wegen der "streng positiven" Bedingung für induktive Datentypen nicht erlaubt.

Ich bin mir nicht sicher, ob ich eine Coq-spezifische Antwort oder eine alternative Implementierung in Haskell anstrebe, die ich in Coq formalisieren kann, aber ich bin glücklich, Vorschläge zu lesen, wie man dieses Problem überwinden kann.


5
2018-04-05 09:24


Ursprung


Antworten:


Sehen Chlipalas "Certified Programming with Dependent Types". Wenn du hättest Definition Id T := T -> T, dann List Id könnte eine nicht-terminierende Laufzeit erzeugen. Ich denke, dass Sie vielleicht auch einen Widerspruch daraus ziehen können Definition Not T := T -> Falsevor allem, wenn Sie die fallenlassen Nil Konstrukteur und akzeptiere das Gesetz der ausgeschlossenen Mitte.

Es wäre schön, wenn es eine Möglichkeit zur Kommentierung gäbe M als nur mit seinem Argument in positiven Lagen. Ich denke, Andreas Abel hat vielleicht etwas in diese Richtung getan.

Wie auch immer, wenn Sie Ihre Datentypen nur ein wenig einschränken möchten, können Sie Folgendes verwenden:

Fixpoint SizedList M A (n : nat) : Type :=
  match n with
    | 0 => unit
    | S m => option (M A * M (SizedList M A m))
  end.

Definition List M A := { n : nat & SizedList M A n }.

3
2018-04-05 10:50