JavaScript:ジェネレータとメモ化を用いた素数列

遅延シーケンスを用いた無限素数列 in JavaScript を読んで勉強になったので、メモ。

• 遅延を用いると素数の計算とかがよりシンプルに記述できる

しかし最終的には効率化のためにメモ化関数にしています。計算には使用してるものの遅延リスト関係なくなっちゃった。

ここではメモ化することを前提に、遅延アイテムとしてジェネレータを使って素数列を作ってみたいと思います。
効率もよくなるだろうし、見た目もいけてる感じになればいいなあ、的なことです。

メモ化関数

一般化されたメモ化関数はこんな感じです。

const memoizer  = inits => rule =>{
  const memo = [...inits]
  return makeA(rule)(memo)
}

const makeA = rule => memo => n => {
  if(n >= memo.length){
    for(let i = memo.length; i < n + 1; i++ ){
      memo[i] = rule( makeA(rule)(memo) )( i )
    }
  }
  return memo[n]
}

初期数列と漸化式っぽい関数を与えることで数列を計算できるようになります。

// 使用例： フィボナッチ数列
const fibo = memoizer([0, 1])(a => n => a(n-1) + a(n - 2))

Array.from({length: 10}, (_, i)=> fibo(i)) 
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ]

ジェネレータ

使用するジェネレータ(と補助的な関数)です。

const succ = x => x + 1

const iterateG = f => n => function*(){
  while(true){
    yield n
    n = f(n)
  }
}()

const mapG = f => g => function*(){
  let x = g.next()
  while( ! x.done ){
    yield f( x.value )
    x = g.next()
  }
}()

const takeWhileG = f => g => function*(){
  let x = g.next()
  while( ! x.done && f(x.value) ) {
    yield x.value
    x = g.next()
  }
}()

const dropWhileG = f => g => function*(){
  let x = g.next()
  while( ! x.done &&  f(x.value) ) x = g.next()
  while( ! x.done ) {
    yield x.value
    x = g.next()
  }
}()

const some = f => g => {
  let x = g.next()
  while( ! x.done ) {
    if( f(x.value)) {
      return true
    }
    x = g.next()
  }
  return false
}

ほぼ元記事に準じてジェネレータ版にしたものです。
mapG は map のジェネレータ版です。前のジェネレータのyield値に関数を適用してyieldします。
succ は数をひとつ増やす関数です。なくてもいいけどよく出てくるので。

素数列を作る

素材がそろったので組み立ててみます。元記事はメソッドチェーンを使っているので見た目の順番は逆ですが、やってることはほぼ同じです。

const primeRule = a => n =>
  dropWhileG(e => some(d => e % d === 0)
                    ( takeWhileG(x => x * x <= e)
                      ( mapG( a )
                        ( iterateG( succ )(0) )
                      )
                    )
            )
    ( iterateG(succ)( a(n - 1) + 1 ) )
  .next().value

const primeInits = [2]

const primeAt = memoizer( primeInits )( primeRule )

// 使ってみる
Array.from({length: 10},(_, i) => primeAt(i))
// [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

やったーできたー。見た目もなんかシンプルでいい感じ。

継続渡しでやってみる

継続を使って元記事と似たような見た目の順番になるようにしてみました、やってることは同じです。

const ret = x => k => k(x)

const primeRule = a => n =>
  ret( iterateG( succ )( a(n - 1) + 1 ) )
    ( dropWhileG(
        e => ret( iterateG( succ )(0) )
               (g => ret( mapG( a )(g) ) )
               (g => ret( takeWhileG(x => x * x <= e)(g) ) ) 
               ( some(d => e % d === 0) )
      )
    )
  .next().value

const primeInits = [2]

const primeAt = memoizer( primeInits )( primeRule )

// 使ってみる
Array.from({length: 10},(_, i) => primeAt(i))
// [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ]

ちょっとゴチャゴチャしてきた印象だけど、これに慣れればこっちの方がむしろ直感的なのかも。