Ich bin neugierig. Ich habe an diesem Datentyp in OCaml gearbeitet :
type 'a exptree =
| Epsilon
| Delta of 'a exptree * 'a exptree
| Omicron of 'a
| Iota of 'a exptree exptree
Was mit explizit typisierten rekursiven Funktionen bearbeitet werden kann (eine Funktion, die erst kürzlich hinzugefügt wurde). Beispiel:
let rec map : 'a 'b. ('a -> 'b) -> 'a exptree -> 'b exptree =
fun f ->
begin function
| Epsilon -> Epsilon
| Delta (t1, t2) -> Delta (map f t1, map f t2)
| Omicron t -> Omicron (f t)
| Iota tt -> Iota (map (map f) tt)
end
Aber ich konnte es nie in Coq definieren :
Inductive exptree a :=
| epsilon : exptree a
| delta : exptree a -> exptree a -> exptree a
| omicron : a -> exptree a
| iota : exptree (exptree a) -> exptree a
.
Coq jammert. Es mag den letzten Konstruktor nicht und sagt etwas, das ich nicht vollständig verstehe oder dem ich nicht zustimme:
Error: Non strictly positive occurrence of "exptree" in "exptree (exptree a) -> exptree a".
Was ich verstehen kann ist, dass induktive Typen, die eine Negation innerhalb ihrer Definition verwenden, type 'a term = Constructor ('a term -> …)
abgelehnt werden, weil sie zu hässlichen, nicht fundierten Tieren wie (untypisierten) λ-Begriffen führen würden. Dieser spezielle exptree
Datentyp scheint jedoch harmlos genug zu sein: Wenn man sich seine OCaml- Definition ansieht , wird sein Argument 'a
niemals in negativen Positionen verwendet.
Es scheint, dass Coq hier übervorsichtig ist. Gibt es also wirklich ein Problem mit diesem speziellen induktiven Datentyp? Oder könnte Coq hier etwas freizügiger sein?
Und was ist mit anderen Beweisassistenten, die in der Lage sind, mit einer solchen induktiven Definition (auf natürliche Weise) umzugehen?
quelle