Created
April 16, 2015 17:10
-
-
Save Adrian2112/57f32a39427df0f3d136 to your computer and use it in GitHub Desktop.
Lazy lists in ruby
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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! | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment