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

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

```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` の定義です.

```javascript
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))) }
```

# 素数列の定義

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

```javascript
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個の素数を列挙

```javascript
primeNumbers.take(100).toString()
```

100未満の素数を列挙

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

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

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

10未満の素数の総和

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

10001番目の素数

```javascript
primeNumbers.drop(10000).car()
```

200万未満の素数の総和

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

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

```javascript
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)
```

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

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

前提知識の再確認と演習, 遅延連結リストの動作原理は [こちら](https://qiita.com/kohyama/items/de0a14c7df3bd65f6777) .