Strutture per la generazione di tipi Haskell a Haskell ( “secondo ordine Haskell”)?

Question

Ci scusiamo in anticipo se questa domanda è un po 'vago. E 'il risultato di qualche sognare ad occhi aperti week-end.

Con il sistema di tipo meraviglioso di Haskell, è deliziosamente piacevole per esprimere la matematica struttura (in particolare algebrica) come typeclasses. Voglio dire, basta dare un'occhiata alla numerico-preludio ! Ma approfittando di tale tipo di struttura meravigliosa, in pratica, è sembrato sempre difficile per me.

Hai un bel modo, il tipo di sistema di esprimere che v1 e v2 sono elementi di un V spazio vettoriale e che w è un elemento di un W spazio vettoriale. Il sistema di tipo consente di scrivere un programma aggiungendo v1 e v2, ma non v1 e w. Grande! Ma, in pratica, si potrebbe desiderare di giocare con potenzialmente centinaia di spazi vettoriali, e certamente non si vuole creare tipi di V1, V2, ..., V100 e dichiarare le istanze del typeclass spazio vettoriale! O forse di leggere alcuni dati dal mondo reale con conseguente simboli a, b e c - si può decidere di esprimere che lo spazio libero vettoriale su questi simboli è davvero uno spazio vettoriale

Quindi sei bloccato, giusto? Al fine di fare molte delle cose che ci piace fare con gli spazi vettoriali in un ambiente di calcolo scientifico, dovete dare il vostro sistema dei tipi rinunciando un typeclass spazio vettoriale e con funzioni fare controlli di compatibilità in fase di esecuzione, invece. Se avete a? Non dovrebbe essere possibile utilizzare il fatto che Haskell è puramente funzionale di scrivere un programma che genera tutti i tipi avete bisogno e li inserisce nel programma vero e proprio? Fa una tale tecnica esiste? Con tutti i mezzi si sottolineano se sto semplicemente si affaccia qualcosa di base qui (probabilmente sono): -)

Modifica Poco fa ho scoperto fundeps . Dovrò pensare un po 'su come si riferiscono alla mia domanda (illuminando commenti per quanto riguarda questo sono apprezzati).

Answer 1

Template Haskell permette questo . Il href="http://www.haskell.org/haskellwiki/Template_Haskell" rel="nofollow"> wiki pagina ha alcuni link utili; particolarmente di Bulat tutorial .

La sintassi di dichiarazione di livello superiore è quello che si desidera. Digitando:

mkFoo = [d| data Foo = Foo Int |]

si genera una giuntura modello di Haskell (come una funzione in fase di compilazione) che creerà una dichiarazione di data Foo = Foo Int semplicemente inserendo la $(mkFoo) riga.

Anche se questo piccolo esempio non è troppo utile, si potrebbe fornire un argomento per mkFoo per controllare il numero delle dichiarazioni differenti che si desidera. Ora un $(mkFoo 100) produrrà 100 nuovi dichiarazioni di dati per voi. È inoltre possibile utilizzare TH per generare istanze di classe tipo. Il mio pacchetto adattativo-tupla è un piccolo progetto che utilizza Template Haskell fare qualcosa di simile.

Un approccio alternativo sarebbe quello di utilizzare Derive , che sarà istanze di classe di tipo automatico Derive . Questo potrebbe essere più semplice se avete solo bisogno le istanze.

Answer 2

Inoltre ci sono alcune semplici tecniche di programmazione di tipo livello in Haskell. Un esempio canonico segue:

-- A family of types for the natural numbers
data Zero
data Succ n

-- A family of vectors parameterized over the naturals (using GADTs extension)
data Vector :: * -> * -> * where
    -- empty is a vector with length zero
    Empty :: Vector Zero a
    -- given a vector of length n and an a, produce a vector of length n+1
    Cons  :: a -> Vector n a -> Vector (Succ n) a

-- A type-level adder for natural numbers (using TypeFamilies extension)
type family Plus n m :: *
type instance Plus Zero n = n
type instance Plus (Succ m) n = Succ (Plus m n)

-- Typesafe concatenation of vectors:
concatV :: Vector n a -> Vector m a -> Vector (Plus n m) a
concatV Empty ys = ys
concatV (Cons x xs) ys = Cons x (concatV xs ys)

Prendetevi un momento per prendere quella in. Penso che sia abbastanza magico che funziona.

Tuttavia, la programmazione tipo di livello in Haskell è nella funzione-inquietante-valley - quel tanto che basta per attirare l'attenzione a quanto non si può fare. lingue dipendente-digitati come Agda , Coq e Epigram prendere questo stile al suo limite e piena potenza.

Modello Haskell è molto più simile al solito stile LISP-macro di generazione del codice. Si scrive il codice per scrivere del codice, allora si dice "ok inserto che qui il codice generato". A differenza della tecnica di cui sopra, è possibile scrivere codice computably specificato in questo modo, ma non ottenere il typechecking molto generale come si vede in concatV sopra.

Così avete alcune opzioni per fare quello che vuoi. Credo che metaprogrammazione è uno spazio davvero interessante, e per certi versi ancora molto giovane. Buon divertimento ad esplorare. : -)