Вычисление функции времени компиляции Haskell
Я хотел бы предварительно вычислить значения для функции во время компиляции.
Пример (реальная функция более сложна, не пытался компилировать):
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 было бы действительно дорогим и будет снова использован многократно.
3 ответа
Вы должны использовать 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-splices. Я написал код шаблона в прямом стиле. Кто-то, более знакомый с TH, должен уметь упростить код шаблона.
Другой вариант - создать таблицу значений в автономном режиме и просто импортировать эту структуру данных.
Вы также можете сказать, почему вы хотите это сделать. Я полагаю, у вас есть очень сложная функция, управляемая таблицами?
Я не знаю никакого способа скомпилировать его в таблицу поиска (хотя вам может повезти с TH). Альтернативой может быть генерация таблицы поиска во время выполнения с помощью чего-то вроде
mymodulus' x = lt ! x
where lt = array (0, 64) [(i, mymodulus i) | i <- [0..64]]
Насколько я помню, определения верхнего уровня связаны с некоторыми особенностями поведения. Если вы попробуете простой пример:
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
Вы Вы увидите, что первый вызов (последних простых чисел) инициирует вычисление простых чисел, а вторая строка будет повторно использовать эти вычисления.