Jestem ciekawy. Pracowałem nad tym typem danych w OCaml :
type 'a exptree =
| Epsilon
| Delta of 'a exptree * 'a exptree
| Omicron of 'a
| Iota of 'a exptree exptree
Z którymi można manipulować za pomocą jawnie wpisanych funkcji rekurencyjnych (funkcja dodana całkiem niedawno). Przykład:
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
Ale nigdy nie byłem w stanie zdefiniować tego w Coq :
Inductive exptree a :=
| epsilon : exptree a
| delta : exptree a -> exptree a -> exptree a
| omicron : a -> exptree a
| iota : exptree (exptree a) -> exptree a
.
Coq marudzi. Nie lubi ostatniego konstruktora i mówi coś, czego nie do końca rozumiem lub z czym się nie zgadzam:
Error: Non strictly positive occurrence of "exptree" in "exptree (exptree a) -> exptree a".
Mogę zrozumieć, że typy indukcyjne wykorzystujące negację w swojej definicji, takie jak, type 'a term = Constructor ('a term -> …)
są odrzucane, ponieważ doprowadziłyby do brzydkich, nieuzasadnionych bestii, takich jak (nietypowane) terminy λ. Jednak ten szczególny exptree
typ danych wydaje się wystarczająco nieszkodliwy: patrząc na jego definicję OCaml , jego argument 'a
nigdy nie jest stosowany w pozycjach ujemnych.
Wygląda na to, że Coq jest tutaj zbyt ostrożny. Czy naprawdę istnieje problem z tym konkretnym rodzajem danych indukcyjnych? A może Coq może być tu nieco bardziej liberalny?
A co z innymi asystentami dowodowymi, czy są w stanie poradzić sobie z taką indukcyjną definicją (w naturalny sposób)?
źródło