lazy evaluation in Ruby&Haskell
lazy evaluation 是函数式编程中的一个重要概念，和传统过程式语言中的cache/state变量恰恰相对；其对应的数值/运算仅仅在用到的时候才实际运算，如果没有调用就什么也不会做。对于构造起来比较昂贵的对象，lazy evaluation可以有效避免cache带来的额外开销，因为只要需要的部分运算被执行，不用的则根本什么也不做。这里以获取Fibonacci数列中的第N个数为例，采用无穷序列的办法比较两种语言的实现。
Haskell 版本
haskell版本的实现如下：
-- lazy evaluation implementation for fibonacci series
fib :: Integer -> Integer -> [Integer]
fib 0 _ = []
fib m n = m : (fib n (m+n))
getIt :: [Integer] -> Integer -> Integer
getIt [] _ = 0
getIt (x:xs) 1 = x
getIt (x:xs) n = getIt xs (n-1)
-- below calculation will end once it's computed though fib function never terminate for large m/n
fetch :: Integer -> Integer -> Integer -> Integer
fetch x y z = getIt (fib x y) z
main = print ( fetch 1 1 10000 )
这里的fib函数返回一个无穷序列，每一项是一个fibo数。getIt函数用于返回第_N_个数。fetch是一个wrapper函数，最后的main函数获取第10000个数作为测试。编译运行如下：
ghc -o fib fib.hs
time ./fib
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
real 0m0.051s
user 0m0.020s
sys 0m0.004s
ruby版本
作为一个非纯函数式语言，缺少pattern matching的支持，ruby版本需要借助lambda技巧来实现无穷序列。类似的版本如下：
class LazyEnumerable
include Enumerable
def initialize(tree)
@tree = tree
end
def each
while @tree
car, cdr = @tree.call
yield car
@tree = cdr
end
end
end
def fib(a, b)
lambda {[a, fib(b, a+b)]}
end
def fetch(a, b, num)
cnt =0
ret = 0
LazyEnumerable.new(fib(a, b)).each do |x|
cnt = cnt + 1
ret = x
#puts "cnt=#{cnt}, num=#{num}, cur = #{x}"
break if cnt == num
end
return ret
end
puts fetch(1,1,10000)实现部分扩展了Enumerable，使之接受一个lambda作为构造参数，通过lambda来达到延迟调用的目的（也就是所谓的lazy).在其each函数中，先获取第一个元素，然后剩下的部分重新赋值给@tree.
运行结果如下：
time ruby lazy_fib.rb
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
real 0m0.251s
user 0m0.132s
sys 0m0.016s
结果比较
两种语言都有GC开销，Ruby版本的实现要比Haskell版本慢了不少，可能的开销主要在于：
- lambda 构造开销
- Dynamic loading的开销，因为Haskell程序是静态编译的
参考链接
- Haskell 例子 来自 haskell wiki
- Ruby 例子 closures in ruby
Leave a Comment
Your email address will not be published. Required fields are marked *