素数の無限ストリームをScalaで

最近、Scalaを勉強しようと思い立った。その結果、

というルーチンが人生で何回目かに起こったので、ブログに自分の言葉で書いておこう。

ストリームと遅延評価

遅延評価

遅延評価は、以下のようなコードで実現出来る。

(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関数である
    • sieve関数は、素数の候補の列を受け取る
    • 先頭の値(ca = (scar stream))を素数として確定する
    • 残りの候補からcaの倍数を除いたストリームを、再度sieveに掛けるというプロミスをcdr部に置く

これによって、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
  }
}

Scalaでは、::がリストを作る演算子で、#::がストリームを作る演算子だそうだ。