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

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