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

JavaScript: クロージャーでメモ化してくれる関数を作ってみた

メモ化っていまいちよくわかっていなかったが、「クロージャを使ってメモ化」を読んで初めてピンときたので、自分でわかるようにES6で書いてみました。

まずは普通に

メモ化してないバージョンのフィボナッチ数列と階乗です。

//フィボナッチ数列
const fibo = n =>
  (n === 0)? 0
  : (n === 1)? 1
  : fibo(n-1) + fibo(n-2)

//階乗
const facto = n =>
  (n === 0)? 1
  : (n === 1)? 1
  : n * facto(n-1)

メモ化した

//フィボナッチ数列
const fibo2 = (
  () =>{
    const memo = [0,1]
    const elem = n =>
      (n >= memo.length)? memo[n] = elem(n-1) + elem(n-2)
      : memo[n]
    return elem
  }
)()

//階乗
const facto2 = (
  () =>{
    const memo = [1,1]
    const elem = n =>
      (n >= memo.length)? memo[n] = n * elem(n-1)
      : memo[n]
    return elem
  }
)()

memoには最初初期値のみが入っていて、memo[n]がなかったら再帰的に計算してmemo[n]に代入しつつ返し、memo[n]があればそれを返す、という作戦です。

メモ化してくれる関数

上のふたつを比べると、初期値と再帰的に計算してる部分が違うだけなので、初期値を inits 、計算規則を rule として引数にくくりだしてみます。

const memoizer = inits => rule =>{
  const memo = [...inits]
  const elem = n =>
    (n >= memo.length)?  memo[n] = rule(elem)(n)
    : memo[n]
  return elem
}

これを使うとそれぞれこうなります。

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

//階乗
const facto3 = memoizer([1,1])( a => n => n * a(n-1) )

それぞれ,
$ a_{0}=0,a_{1}=1,a_{n}=a_{n-1}+a_{n-2} $

$ a_{0}=1,a_{1}=1,a_{n}=n a_{n-1} $
に、見えてきません?
こうしておくと、初期値と漸化式で表わされる数列が簡単にメモ化して使える。便利かも。

おまけ:

何が起きてるか見たかったので適当にログを吐くようにしてみました。

const memoizer_log = inits => rule =>{
  const memo = [...inits]
  const elem = n =>
    (n >= memo.length)?  
      (console.log(`memo[${n}]? So,calc it.`)
      , memo[n] = rule(elem)(n)
      , console.log(`Set memo[${n}]=${memo[n]} and return it.`)
      , memo[n]
      )
    : 
      (console.log(`Return ${memo[n]} from memo[${n}].`)
      , memo[n]
      )
  return elem
}

//使用例
> const fibo4 = memoizer_log([0, 1])( a => n => a(n-1) + a(n-2) )
=> undefined

> fibo4(5)
memo[5]? So,calc it.
memo[4]? So,calc it.
memo[3]? So,calc it.
memo[2]? So,calc it.
Return 1 from memo[1].
Return 0 from memo[0].
Set memo[2]=1 and return it.
Return 1 from memo[1].
Set memo[3]=2 and return it.
Return 1 from memo[2].
Set memo[4]=3 and return it.
Return 2 from memo[3].
Set memo[5]=5 and return it.
=> 5

> fibo4(5)
Return 5 from memo[5].
=> 5

> fibo4(6)
memo[6]? So,calc it.
Return 5 from memo[5].
Return 3 from memo[4].
Set memo[6]=8 and return it.
=> 8