Route 477

■ [haskell][ruby] 木構造を用いた純粋関数的なメモ化

• Haskellでメモ化を行うもう一つの方法 - 純粋関数型雑記帳

メモ化というと配列とかでテーブル作るのが普通だけど、それをHaskellで「無限ツリー」を使ってpurely functionalにしてみた、という話。

結構前の記事ですが、面白かったのでRubyに移植を試みてみた。

# "添字の上位ビットからみて、ツリーを辿っていくだけです。" が分からなかったので
# 図を書いてみる：
# * n
#          0
#     1           2
#   3    4     5     6
# 7  8 9  10 11 12 13 14
# 
# * n+1の2進表現(_は1です)
#                   _
#         _0                  _1
#   _00       _01       _10       _11
#_000 _001 _010 _011 _100 _101 _110 _111
#
# 確かに、上位ビットから順に「0＝左・1＝右」として木をたどればいいようになっている…

class InfTree
  def initialize(func, ix)
    @func, @ix = func, ix
  end

  def value
    if @value
      puts "reuse #{@ix}"
      @value
    else
      puts "calc: #{@ix}"
      @value = @func[@ix]
    end
  end

  def left
    @left ||= InfTree.new(@func, @ix*2+1)
  end

  def right
    @right ||= InfTree.new(@func, @ix*2+2)
  end
end

# find_tree: (Tree Int) -> Int -> Int
def find_tree(tree, ix)
  bits = (ix+1).to_s(2).chars.drop(1) 
  _find(tree, bits)
end
def _find(tr, bs)
  case bs.first
  when nil
    tr.value
  when "0"
    _find(tr.left, bs.drop(1))
  when "1"
    _find(tr.right, bs.drop(1))
  else
    raise
  end
end

# memo: (Int -> Int) -> (Int -> Int)
def memo(func)
  tree = InfTree.new(func, 0)
  ->(n){
    find_tree tree, n
  }
end

# fib: Int -> Int
fib = memo(->(n){
  if n < 2
    n
  else
    fib[n-1] + fib[n-2]
  end
})

p fib[100]