遅延シーケンスを用いた無限素数列 in JavaScript

JavaScript で Project Eular に挑む後輩のために, 過去の記事
https://qiita.com/kohyama/items/b0f87160605560bae2f8
でご紹介しました, Clojure による素数列の定義

(def prime-numbers
  ((fn f [x]
     (cons x
       (lazy-seq
         (f (first
              (drop-while
                (fn [n]
                  (some #(zero? (mod n %))
                    (take-while #(<= (* % %) n) prime-numbers)))
                (iterate inc (inc x))))))))
   2))

を, なるべくそのままのアルゴリズムで JavaScript で実装します.

遅延連結リスト

準備として, 遅延シーケンスの実現方法として, 遅延連結リスト (次の要素を指す部分が遅延評価させられるようになっている連結リスト) を実装します.
また, 上記アルゴリズムの再現に必要な関数も用意します.

以下が, 遅延連結リスト LazyLinkedList のコンストラクタ,
インスタンスメソッド car, cdr, reduce, take, drop, takeWhile, dropWhile, some, toString,
生成系の関数 cons, iterate の定義です.

function LazyLinkedList (a, b) {
  this.car = () => a
  this.cdr = b
  this.reduce = function (f, a) {
    if (a == null)
      return this.cdr().reduce(f, this.car())
    let l = this
    while (l.car() != null) {
      a = f(a, l.car())
      l = l.cdr()
    }
    return a
  } 
  this.take = function (n) {
    return (n == 0)
      ? cons(null, () => null)
      : cons(this.car(), () => this.cdr().take(n - 1))
  }
  this.drop = function (n) {
    let l = this
    while (0 < n--)
      l = l.cdr()
    return l
  }
  this.takeWhile = function (p) {
    return p(this.car())
      ? cons(this.car(), () => this.cdr().takeWhile(p))
      : cons(null, () => null)
  }
  this.dropWhile = function (p) {
    let l = this
    while (p(l.car()))
      l = l.cdr()
    return l
  }
  this.some = function (p) {
    let l = this
    while (l.car() != null && !p(l.car()))
      l = l.cdr()
    return l.car()
  }
  this.toString = function (f) {
    return (this.car() == null)?"":(this.car() + ", " + this.cdr().toString())
  }
}
const cons = (a, b) => new LazyLinkedList(a, b)
function iterate (f, a) { return cons(a, () => iterate(f, f(a))) }

素数列の定義

そうすると素数列は次のように書けます.

const primeNumbers = (function f(x) {
  return cons(x,
    () => f(
      iterate(n => n + 1, x + 1)
        .dropWhile(
           n => primeNumbers
                  .takeWhile(c => c*c <= n)
                  .some(d => n%d == 0))
        .car()))
})(2)

素数列は『見つかっているうちの最後の素数 x を与えると「自分自身 f に, x の次の素数を与えて得られる遅延シーケンス f(...)」 の先頭に x を付加する cons(x, () => ...) ような関数 f』に 2 を与えたものです.

ただし x の次の素数は, x より 1 大きい数から, 1ずつ大きくなる数列 iterate(...) の要素を, 『自然数 n を与えると, 素数列 primeNumbers の先頭から, 二乗が n 以下である間, 要素を取り出した列 .takeWhile(...) の中に n を割り切るものがあれば真を返すような関数 .some(...)』に与えて, 真を返す間の要素を捨てたもの dropwhile(...) の最初の要素 .car(...) です.

素数列を求めるのに素数列を使っていますが, 次の素数の候補に対して, 二乗がその数以下であるような素数までは求まっているので, 大丈夫.
遅延シーケンス万歳！

動作確認

以下で動作確認してみてください.

2から昇順100個の素数を列挙

primeNumbers.take(100).toString()

100未満の素数を列挙

primeNumbers.takeWhile(n => n < 100).toString()

9000以上, 10000未満の素数を列挙

primeNumbers.dropWhile(n => n < 9000).takeWhile(n => n < 10000).toString()

10未満の素数の総和

primeNumbers.takeWhile(n => n < 10).reduce((a, x) => a + x)

10001番目の素数

primeNumbers.drop(10000).car()

200万未満の素数の総和

primeNumbers.takeWhile(n => n < 2000000).reduce((a, x) => a + x)

と思ったけど, 10分待っても終わらないので, メモ化して再挑戦.

const primeNumbersWithMemoize = (function () {
  let memo = {}
  return function f(x) {
           if (!memo[x]) {
             memo[x] = cons(x,
                         () => f(
                           iterate(n => n + 1, x + 1)
                             .dropWhile(
                               n => primeNumbersWithMemoize
                                      .takeWhile(c => c*c <= n)
                                      .some(d => n%d == 0))
                             .car()))
           }
           return memo[x]
         }
})()(2)

primeNumbersWithMemoize.takeWhile(n => n < 2000000).reduce((a, x) => a + x)

手元の環境では計算に 7 分かかりました.
競技プログラミングでは制限時間超過ですね...

前提知識の再確認と演習, 遅延連結リストの動作原理は こちら .