8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-02-12

背景

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

参考

8
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?