Расчет функции времени компиляции Haskell

Question

Я хотел бы предварительно вычислить значения для функции во время компиляции.

Пример (реальная функция является более сложной, не пересобирать):

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 

Я знаю, что mymodulus n будет вызываться только с n < 64, и я хотел бы предвычислять mymodulus для n значений 0..64 во время компиляции. Причина в том, что mymodulus будет действительно дорогим и будет многократно использоваться повторно.

Answer 1

Вы должны использовать Template Haskell. С помощью TH вы можете генерировать код программно, во время компиляции. В этом случае ваш mymodulus является «шаблоном».

Например, мы можем переписать вашу программу следующим образом, чтобы вычислить вашу функцию статически. первый, основной код, как обычно, но вместо вызова вашей функции модуля, он вызывает функцию, тело сплайсинг, который будет генерироваться во время компиляции:

{-# LANGUAGE TemplateHaskell #-} 

import Table 

mymodulus n = $(genmodulus 64) 

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

И код для создания таблиц статический:

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

Это описывает абстрактный синтаксис выражения case, который будет сгенерирован во время компиляции. Мы просто генерируем большой переключатель:

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

Вы можете видеть, какой код сгенерирован с помощью -ddump-сращиваний. Я написал код шаблона в прямом стиле. Кто-то, более знакомый с TH, должен иметь возможность сделать код шаблона более простым.

Другим вариантом является создание таблицы значений в автономном режиме и просто импорт этой структуры данных.

Вы также можете сказать, почему вы хотите это сделать. Я предполагаю, что у вас очень сложная функция, управляемая таблицами?

Answer 2

Я не знаю, как прекомпилировать его до поиска таблицы (хотя вам может быть повезло с TH). Альтернатива для создания таблицы, если поиск во время выполнения с чем-то вроде

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

Answer 3

Как я помню, существует определенное поведение, связанное с определениями верхнего уровня. Если вы попытаетесь простой пример:

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 

Вы увидите, что первый вызов (последних простых чисел) будет инициировать вычисление простых чисел и второй линии будет повторно использовать эти расчеты.