Promozione tipo di dati per le persone con problemi di dipendenza

Question

Dopo aver letto il file ghc 7.4. note pre-rilascio e il documento Giving Haskell a Promotion, sono ancora confuso su ciò che effettivamente si fa con i tipi promossi. Ad esempio, il manuale di GHC ha pronunciato la seguente esempi sui tipi di dati promosse:

data Nat = Ze | Su Nat 

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

data Pair a b = Pair a b 

data Sum a b = L a | R b 

Che tipo di usi fare queste hanno come genere? Puoi dare esempi (di codice)?

Answer 1

Nat può essere ad es. utilizzato per costruire vettori numerici che possono essere aggiunti solo se hanno la stessa lunghezza, controllati allo tempo di compilazione.

Answer 2

Ci sono almeno due esempi nella carta stessa:

"1. Introduzione" dice: "Per esempio, potremmo essere in grado di garantire [in fase di compilazione] che un presunto albero rosso-nero ha davvero la proprietà rosso-nero ".

"2.1 Promoting datatypes" illustra i vettori indicizzati in base alla lunghezza (ovvero i vettori con errori "index out of bounds" in fase di compilazione).

Puoi anche dare un'occhiata ai lavori precedenti in questa direzione, ad es. Libreria HList per liste eterogenee sicure per tipo e collezioni estensibili. Oleg Kiselyov ha molte opere correlate. Puoi anche leggere i lavori sulla programmazione con tipi dipendenti. http://www.seas.upenn.edu/~sweirich/ssgip/main.pdf ha esempi introduttivi per calcoli a livello di codice in Agda, ma questi possono essere applicati anche ad Haskell.

Approssimativamente, l'idea è che per gli elenchi head venga fornito un tipo più preciso. Invece di

head :: List a -> a 

è

head :: NotEmptyList a -> a 

La funzione testa Quest'ultimo è più typesafe del fomer: non può mai essere applicato a liste vuote perché causerebbe errori di compilazione.

Sono necessari calcoli a livello di codice per esprimere tipi come NotEmptyList. Digitare classi con dipendenze funzionali, GAGT e famiglie di tipi (indicizzati) forniscono già forme deboli di calcoli a livello di codice per haskell. Il lavoro che hai citato si sviluppa ulteriormente in questa direzione.

Vedere http://www.haskell.org/haskellwiki/Non-empty_list per un'implementazione utilizzando solo classi di tipi Haskell98.