Strutture dati con componenti non deterministici in Coq

Question

Ho provato a modellare una codifica monadica meno ingenua del non-determinismo (meno ingenuo di MonadPlus e liste comuni) in Coq che è spesso usato in Haskell; ad esempio la codifica per gli elenchi è simile a

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

mentre la corrispondente definizione in Coq vorrebbe come segue.

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

Tuttavia, questo tipo di definizione non è consentito in Coq a causa della Circostanza "strettamente positiva" per i tipi di dati induttivi.

Non sono sicuro di puntare a una risposta specifica di Coq oa un'implementazione alternativa in Haskell che posso formalizzare in Coq, ma sono felice di leggere qualsiasi suggerimento su come superare questo problema.

Answer 1

Vedere Chlipala's "Certified Programming with Dependent Types". Se avessi Definition Id T := T -> T, allora List Id potrebbe produrre un termine non terminante. Penso che potresti anche essere in grado di derivare una contraddizione dal Definition Not T := T -> False, specialmente se lasci il costruttore Nil e accetti la legge del mezzo escluso.

Sarebbe bello se ci fosse un modo per annotare M come solo utilizzando il suo argomento in posizioni positive. Penso che Andreas Abel abbia forse lavorato in questa direzione.

In ogni caso, se siete disposti a limitare le tipi di dato solo un po ', si potrebbe usare:

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 }.