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

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

7 голосов
/ 19 марта 2010

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

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

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 ]

13 голосов
/ 19 марта 2010

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

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

{-# 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, сможет упростить код шаблона.

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

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

2 голосов
/ 19 марта 2010

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

mymodulus' x = lt ! x
    where lt = array (0, 64) [(i, mymodulus i) | i <- [0..64]]
0 голосов
/ 20 марта 2010

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

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

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

...