遅延評価

lambdaを使えば遅延評価が出来ると知ったので，たらい回し関数でテストしてみる．たらい回し関数は青木日記 2003-03-15から持ってきた．

def tarai( x, y, z )
  if x <= y
  then y
  else tarai(tarai(x-1, y, z),
             tarai(y-1, z, x),
             tarai(z-1, x, y))
  end
end

p tarai(12, 6, 0)
#=> 12

まじめに計算すると10秒掛かる．

class Lazy
  def initialize(&block)
    @val,@block = nil, block
  end
  def val
    @val ||= @block.call()
  end
end

def lazy(&block); Lazy.new(&block); end

def lazy_tarai(ax,ay,az)
  f = lambda {|x,y,z|
    if x <= y
      y
    else 
      f[     f[ x-1,     y,     lazy{z.val}],
             f[ y-1,     z.val, lazy{x}    ],
        lazy{f[ z.val-1, x,     lazy{y}    ]}]
    end
  }
  f[ax,ay, lazy{az}]
end
p lazy_tarai(120, 60, 0)
#=> 120

12だと一瞬で終わるので，120でテスト．それでも0.7秒程度．
本当ならx,yもlazyにするんだろうけど，必ず最初に評価されるので，lazyにする意味はないと思って，zのみ遅延評価するようにしてみた．

追記：
青木日記 2003-03-23
青木日記 2003-04-11
青木日記 2003-04-20
青木日記 2003-04-25

一番最後のバージョンをうちで実行したら，120で0.01秒…．すごすぎ．