Calcolo della funzione del tempo di compilazione Haskell

Question

Vorrei precalcolare i valori per una funzione in fase di compilazione.

Esempio (funzione reale è più complessa, non abbiamo provato la compilazione):

base = 10 
mymodulus n = n `mod` base -- or substitute with a function that takes 
          -- too much to compute at runtime 
printmodules 0 = [mymodulus 0] 
printmodules z = (mymodulus z):(printmodules (z-1)) 

main = printmodules 64 

io so che mymodulus n si chiamerà solo con n < 64 e vorrei precalculate mymodulus per n valori di 0..64 al momento della compilazione. Il motivo è che mymodulus sarebbe molto costoso e verrà riutilizzato più volte.

Answer 1

Si dovrebbe usare Template Haskell. Con TH è possibile generare codice a livello di codice, in fase di compilazione. In questo caso il tuo mymodulus è effettivamente un "modello".

Ad esempio, è possibile riscrivere il programma come segue, per calcolare staticamente la funzione. In primo luogo, il codice principale, come al solito, ma invece di chiamare la funzione modulo, si chiama una funzione il cui corpo è una giunta che verrà generato in fase di compilazione:

{-# LANGUAGE TemplateHaskell #-} 

import Table 

mymodulus n = $(genmodulus 64) 

main = mapM_ (print . mymodulus) [0..64] 

E il codice per generare la tabella staticamente:

{-# LANGUAGE TemplateHaskell #-} 

module Table where 

import Language.Haskell.TH 
import Language.Haskell.TH.Syntax 

genmodulus :: Int -> Q Exp 
genmodulus n = return $ CaseE (VarE (mkName "n")) 
           [ Match (LitP (IntegerL i)) 
             (NormalB (LitE (IntegerL (i `mod` base)))) 
             [] 
           | i <- [0..fromIntegral n] ] 
    where 
     base = 10 

Descrive la sintassi astratta dell'espressione case, che verrà generata in fase di compilazione. Abbiamo semplicemente generiamo un grande interruttore:

genmodulus 64 
    ======> 
    case n of { 
     0 -> 0 
     1 -> 1 
     2 -> 2 
     3 -> 3 
     4 -> 4 
     ... 
     64 -> 4 } 

Si può vedere ciò che il codice viene generato con -ddump-giunzioni. Ho scritto il codice del modello in stile diretto. Qualcuno più familiare con TH dovrebbe essere in grado di rendere più semplice il codice del pattern.

Un'altra opzione sarebbe quella di generare una tabella di valori offline e importare semplicemente quella struttura di dati.

Si potrebbe anche dire perché si desidera fare questo. Suppongo tu abbia una funzione molto complessa basata su tabelle?

Answer 2

Non conosco alcun modo per precompilarlo in una tabella di ricerca (anche se potresti avere un po 'di fortuna con TH). Un'alternativa è quella di generare una tabella una ricerca in fase di esecuzione con qualcosa di simile

mymodulus' x = lt ! x 
    where lt = array (0, 64) [(i, mymodulus i) | i <- [0..64]] 

Answer 3

Come ricordo, vi è un comportamento speciale associato alle definizioni di livello superiore. Se si tenta semplice esempio:

primes = 2 : 3 : filter isPrime [5, 7 .. 1000000] 
isPrime x = walk (tail primes) where 
    walk (y:ys) | (y*y > x) = True 
       | (x `mod` y) /= 0 = walk ys 
    walk _ = False 
main = do 
    print $ last primes 
    print . last $ init primes 

Vedrai che prima convocazione (ultimi numeri primi) avvierà il calcolo dei numeri primi e seconda linea riutilizzerà questi calcoli.