背景
Haskellでは、常に同じ値を返す定数関数であっても、評価されるたびに計算が行われるらしい(間違ったこと言ってたら指摘してください)。
プロジェクト・オイラーをやっていて、ふるいで作った素数表を使って素因数分解したいのだが、素因数分解は何回も行うので、そのたびにふるい関数が評価されて時間がかかるのを避けたい。定数は1回計算したら値を覚えておいてくれればいいのに。
解決法
Template Haskellを使うとコンパイル時に計算され、実行時間は一瞬になる。
module SlowSieve where
sieve :: [Integer] -> [Integer]
sieve [] = []
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
main = print $ sieve [2..100000]
{-# LANGUAGE TemplateHaskell #-}
import SlowSieve hiding (main)
main = print $( let x = sieve [2..100000] in [| x |] )
Template Haskellを使う場合はこのように別モジュールに分けないといけないらしい。
Template Haskellの機能はこのような定数計算のためだけにあるわけではなく、#defineのような(?)コンパイル時メタプログラミングができるらしい。