Cálculo de la función de tiempo de compilación Haskell

Question

Me gustaría precalcular valores para una función en tiempo de compilación.

Ejemplo (función real es más compleja, no trató de compilar):

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 

Yo sé que mymodulus n se llamará únicamente con n < 64 y me gustaría precalcular mymodulus para n valores de 0..64 en tiempo de compilación La razón es que mymodulus sería realmente costoso y se reutilizará varias veces.

Answer 1

Debe utilizar Template Haskell. Con TH puede generar código programáticamente, en tiempo de compilación. Su mymodulus es efectivamente una "plantilla" en este caso.

Por ejemplo, podemos reescribir su programa de la siguiente manera, para calcular su función estáticamente. En primer lugar, el código principal, como de costumbre, pero en lugar de llamar a su función de módulo, se llama a una función cuyo cuerpo es un empalme que se generará en tiempo de compilación:

{-# LANGUAGE TemplateHaskell #-} 

import Table 

mymodulus n = $(genmodulus 64) 

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

Y el código para generar la tabla de forma estática:

{-# 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 

Esto describe la sintaxis abstracta de la expresión de caso, que se generará en tiempo de compilación. Simplemente, generamos un gran cambio:

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

Se puede ver qué código se genera con -ddump-empalmes. He escrito el código de la plantilla en estilo directo. Alguien más familiarizado con TH debería ser capaz de simplificar el código de patrón.

Otra opción sería generar una tabla de valores fuera de línea e importar esa estructura de datos.

También podría decir por qué desea hacer esto. ¿Supongo que tiene una función muy compleja basada en tablas?

Answer 2

No conozco ninguna forma de precompilarlo hasta la búsqueda de una tabla (aunque puede tener algo de suerte con TH). Una alternativa es generar una tabla de operaciones de búsqueda en tiempo de ejecución con algo como

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

Answer 3

Como recuerdo, hay un comportamiento especial asociado a las definiciones de nivel superior. si usted intenta ejemplo sencillo:

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 

Vas a ver que la primera llamada de (últimos números primos) iniciará el cálculo de los números primos y segunda línea se vuelva a usar esos cálculos.