Lazy lists in ruby

lazy-lists.rb

#Lazy evaluation

mult_2 = lambda {|x| x*2}
square = lambda {|x| x**2}
div_2 = lambda {|x| x/2}

# just a function to show every step we are doing
# receives a function that will be passed to directly as the map function
# and a step number just to print it out
print_s = lambda { |fn,s| lambda { |x| puts "step #{s} => #{x}"; fn[x] } }

(1..10).map(&print_s[mult_2, 1]).map(&print_s[square,2]).map(&print_s[div_2,3]).first(3)
# step 1 => 1
# step 1 => 2
# step 1 => 3
# step 1 => 4
# ...

# here we are using the ruby 2 lazy enumerator
(1..10).lazy.map(&print_s[mult_2, 1]).map(&print_s[square,2]).map(&print_s[div_2,3]).first(3)
# step 1 => 1
# step 2 => 2
# step 3 => 4
# step 1 => 2
# ...
# notice the diference in the order of the steps numbers. Previously we had the first map applied to all the elements then the second one, then the third one.
# here we apply first map to the first argument, then second map to the result then the third one. We start applying the same thing to the second argument.

#
# infinite lists
infinity = 1.0/0
(1..infinity).map(&print_s[mult_2, 1]).map(&print_s[square,2]).map(&print_s[div_2,3]).first(3) #never ends
(1..infinity).lazy.map(&print_s[mult_2, 1]).map(&print_s[square,2]).map(&print_s[div_2,3]).first(3)

###
# an example using lazy infinite lists
fib = lambda do |x|
  if x== 1 || x == 0
    1
  else
    fib[x-1] + fib[x-2]
  end
end

# problem: find x where fib[x] > 100 ? => #find… but using select…
# we dont know which number has a fibonacci > 100 so we start trying with different ranges
(1..3).select{|x| fib[x] > 100 }.first #nope
(1..4).select{|x| fib[x] > 100 }.first #nope

# … mmm what if we give a big range
(1..100).select{|x| fib[x] > 100 }.first
# never going to finish (some day… probably) we have to calculate the fibonacci for the whole list so we can get the first element that matches the filter
# fib[30] starts to take a while and the time to calculate grows exponentially (there is a better way to implement fibonacci, but this is ok for ilustration purposes)

# ok so what if we use a lazy list
(1..100).lazy.select{|x| fib[x] > 100 }.first # wooh! we only calculate for the numbers before we find the one we want

# what if we the x where fib[x] > an unknown number for us
# we could make the range bigger (1..1000) but probably the number is not in that range.
# well, then lets make an infinite list and x SHOULD be there
(1..infinity).lazy.select{|x| fib[x] > 600 }.first # wooh!