skyscribe.programming.thinking

汇小流以成江海，积跬步以至千里

Lazy Evaluation in Ruby&Haskell

| Comments

lazy evaluation 是函数式编程中的一个重要概念，和传统过程式语言中的cache/state变量恰恰相对；其对应的数值/运算仅仅在用到的时候才实际运算，如果没有调用就什么也不会做。对于构造起来比较昂贵的对象，lazy evaluation可以有效避免cache带来的额外开销，因为只要需要的部分运算被执行，不用的则根本什么也不做。这里以获取Fibonacci数列中的第N个数为例，采用无穷序列的办法比较两种语言的实现。

Haskell 版本

haskell版本的实现如下：

fib.hs (fib.hs) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-- 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个数作为测试。编译运行如下：

1
2
3
4
5
6
7

ghc -o fib fib.hs
time ./fib
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

real    0m0.051s
user    0m0.020s
sys 0m0.004s

ruby版本

作为一个非纯函数式语言，缺少pattern matching的支持，ruby版本需要借助lambda技巧来实现无穷序列。类似的版本如下：

lazy_fib.rb (lazy_fib.rb) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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.

运行结果如下：

1
2
3
4
5
6

time ruby lazy_fib.rb
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

real    0m0.251s
user    0m0.132s
sys 0m0.016s

结果比较

两种语言都有GC开销，Ruby版本的实现要比Haskell版本慢了不少，可能的开销主要在于： – lambda 构造开销 – Dynamic loading的开销，因为Haskell程序是静态编译的

参考链接

Comments