JavaScript
es6
関数型プログラミング

参照記事:
99 Haskell Problems より、[31] でもその前に
Haskellで素数 2 自分でもやってみた。
Pythonで素数 2 Pythonでやってみた。この記事はこれの改良版です。
Javascript: スプレッド構文とジェネレーターを使ってtransducerっぽいことをする ジェネレーター関連のこと。 本題からずれて無駄に難しくなるので、関数合成関連のコードは削除しました。

Haskell界隈でやられている方法を以前教えていただいたので、JavaScriptでどうできるか、やってみました。
理屈はめんどくさいですが、何かと効率がいいようです。

letとかwhileとか使いまくりで、何が関数型か?思いっきり手続き型じゃない?という感じですが、Haskellの遅延評価を使ったクールなコードを、何とかJavaScriptのジェネレーターで実現しようとした爪痕です。
暖かい眼で見てやってください。

//最大公約数。
const gcd = x => y => y === 0 ? x : gcd( y )( x % y )

// 配列をジェネレーターにする。
const arrayToG = xs => function*(){
    yield* xs;
}();

// s から p*p-2 までの素数の候補を返すジェネレーター。2と3の倍数を除いたもの(になるはず)。
const croppedPrimables = s => p => function*(){
  let x = s;
  yield x;
  while( (x=x+4) <= p * p - 2 ){
    yield x;
    if( (x=x+2) <= p * p - 2 ){
      yield x;
    } else {
      return;
    }
  }
}();

//s から p*p-2 までの素数を返すジェネレーター。
const zonedPrimes = m => s => p => function*(){
  const nG = croppedPrimables(s)(p);
  let x;
  while(!( x = nG.next()).done ){
    if(gcd(m)(x.value) === 1)yield x.value;
  }
}();

//素数を返すジェネレーター。
const primes = () => function*(){
  let x;
  let primeG = arrayToG([2, 3, 5]);
  let [m, s, p] = [1, 7, 5];

  let y;
  let seedG = arrayToG([]);
  let [m1, s1, p1] = [1, 7, 5];

  while(true){
    while( !( x = primeG.next() ).done ) yield x.value;
    primeG = zonedPrimes(m)(s)(p);

    if( ( y = seedG.next() ).done ){
      seedG = zonedPrimes(m1)(s1)(p1);
      y = seedG.next();
      [m1, s1, p1] = [ m1 * p1 , p1 * p1 , y.value ];
    }

    [m, s, p] = [ m * p , p * p , y.value ];
  }
}();

//100以下の素数を表示する。
{
  const primesGen = primes();
  let x;
  while((x = primesGen.next()).value <= 100) console.log(x.value);
}
//=>結果
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

仕組み

ジェネレーター croppedPrimable は:

  • 引数sに6n+1型の整数をとることで
  • p^2-2 までの2と3の倍数を除いた素数候補を、
  • 呼ばれるたびに一個ずつ返します。

なんでわざわざこんなことを?とも思うのですが、次の素数を選別する処理が重くてロスが大きいので、なるべく候補を絞って効率良く、ということなのでしょうたぶん。

ジェネレーター zonedPrimes は:

  • croppedPrimables(s)(p)から一個ずつ値をとり
  • mとの最大公約数が1になる値を一個ずつ返します。

mには、最初は1、その後、2,3を除いたp未満の素数(5,7,11...)を全てかけた数がはいります。

ジェネレーターprimesは呼ばれるたびに素数を一個ずつ返します。
内部にふたつのジェネレーターがあります。

  • primeG(初期値[2,3,5]):外部に素数を返す用
  • seedG(初期値[]):内部でprimeG の再充填に使う p を供給する用

ふたつとも素数を返すジェネレーターに違いはありませんが、値を消費する速度がだいぶ違います。
このふたつを使ってhaskellの遅延評価の部分をなんとか実現しようとしています。

  • primeGが素数を一個ずつ返し、
  • primeGが空になったら、primeGを再充填する
  • seedGから値をひとつとり
    • このときseedGが空なら、
      • seedGを再充填して
      • seedGから値をひとつとり、
      • seedGの再充填のためのパラメータを設定する
  • primeGの再充填のためのパラメータを設定する

という流れです。