素数の無限ストリームをScalaで
最近、Scalaを勉強しようと思い立った。その結果、
- Project Eulerを解く
- 素数の無限列が欲しくなる
- どうするんだっけ?
- SICPを読む
というルーチンが人生で何回目かに起こったので、ブログに自分の言葉で書いておこう。
ストリームと遅延評価
遅延評価
遅延評価は、以下のようなコードで実現出来る。
(define (memoize func) (define evaled #f) (define val ()) (lambda () (cond (evaled val) (else (set! evaled #t) (set! val (func)) val)))) (define-syntax my-delay (syntax-rules () ((_ exp) (memoize (lambda () exp))))) (define (my-force promise) (promise))
- my-delayで、与えられた式を遅延して評価するpromiseを作成する
- my-delayは、実際にはlambdaで式を囲んだクロージャーを返すだけ
- my-delayは、関数ではなくて、マクロとして定義する必要がある
- そうでないと、引数のexpが即座に評価されてしまう
- 2回目以降の評価時は前回の結果を返せば良いので、メモ化をしている(memoize)
- my-forceで、promiseを実際に評価する
- これは、単純にpromiseを評価するだけ
ストリーム
リストが
- 先頭の要素、と
- それ以降の要素のリスト
のペアであるのと同じように、ストリームは
- 先頭の要素、と
- 評価されるとストリームになるpromise
のペアである。ストリームを生成・操作する関数は以下のように実装出来る。
(define-syntax scons (syntax-rules () ((_ ca cd) (cons ca (my-delay cd))))) (define scar car) (define (scdr stream) (my-force (cdr stream)))
- sconsで、ストリームを作る
- sconsは関数ではなくて、マクロとして定義されなければならない
- そうでないと、cdが即座に評価されてしまう
- scarは単純にペアの左を返せば良い
- scdrは、ペアの右をforceして返す
無限ストリーム
ストリームに対してscdrを実行するとストリームが返ってくるのだが、どんだけscdrを掛けても決して空ストリームが返ってこないようなストリームを定義すれば、無限ストリームが実現出来る。これが出来るのは、cdr部の評価をforceされるまで保留しているからで、リストで同じ事をやると、永遠にそのリストの評価が終わらない事になる。
例えば、整数全体の列は
(define (num-from n) (scons n (num-from (+ n 1)))) (define integers (num-from 1))
のように定義出来る。
素数の無限列
エラトステネスの篩の手続きを思い出す。
最初、素数の候補の全体は、2以上の整数全体である。この候補のうち、最小の数2は、絶対に他の数で割り切れないので、素数である事が確定する。2が素数であることが確定すると、2の倍数は全て素数ではないことが分かるので、素数の候補を、整数全体から2の倍数を除いたものに絞る事が出来る。次に、新しい候補のリストの中で最小の数3が、同様に素数であることが確定し、同じく、候補リストから3の倍数を除外する事が出来る。
つまり、
- 候補のリストを受け取る
- 先頭を素数として確定
- 候補から先頭要素の倍数を除外
という操作を続ければ、延々と素数の列が得られる。これをストリームとして実現するには、以下のようにすれば良い。
(define (sfilter pred stream) (let ((ca (scar stream)) (cd (scdr stream))) (if (pred ca) (scons ca (sfilter pred cd)) (sfilter pred cd)))) (define (sieve stream) (let* ((ca (scar stream)) (cd (scdr stream)) (pred (lambda (n) (not (= 0 (mod n ca)))))) (scons ca (sieve (sfilter pred cd))))) (define primes (sieve (num-from 2)))
- まず、ストリームから特定の条件を満たすものだけを残すsfilterを定義する
- エラトステネスの篩の操作を実現するのが、sieve関数である
これによって、primesのscdrを評価していけば、素数の無限列が得られる。
Scalaでは
Scalaでは、以下のように書ける
object Primes { val primes = sieve(Stream.from(2)) def sieve(st: Stream[Int]): Stream[Int] = { val x = st.head x #:: sieve(st.tail.filter(_ % x != 0)) } def main(args: Array[String]): Unit = { println(primes.take(10).map(_.toString).reduce("%s, %s".format(_, _))) // => 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 } }