3
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

posted at

updated at

Organization

Template Haskellを使って定数をコンパイル時に計算しておく

背景

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のような(?)コンパイル時メタプログラミングができるらしい。

参考

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
3
Help us understand the problem. What are the problem?