This class implements lazy lists (or streams) for Ruby. Such lists avoid the computation of values which aren’t needed for some computation. So it’s possible to define infinite lists with a limited amount of memory. A value that hasn’t been used yet is calculated on the fly and saved into the list. A value which is used for a second time is computed only once and just read out of memory for the second usage.
Florian Frank flori@ping.de
This is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License Version 2 as published by the Free Software Foundation: www.gnu.org/copyleft/gpl.html
The latest version of this library can be downloaded at
The homepage of this library is located at
To compute the square numbers with a lazy list you can define one as
![[+]](./images/find.png "show/hide quicksearch"){kind=small}
sq = LazyList.tabulate(1) { |x| x * x }
or in the much nicer list builder syntax:
sq = list { x * x }.where :x => 1..Infinity
Now it’s possible to get the first 10 square numbers by calling LazyList#take
sq.take(10)
===>[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
To compute the first 10 square numbers and do something with them you can call the each method with:
sq.each(10) { |x| puts x }
To compute every square number and do something with them you can call the “each” method without an argument:
sq.each { |x| puts x }
Notice that calls to each without an argument will not return if applied to infinite lazy lists.
You can also use indices on lazy lists to get the values at a certain range:
sq[ 0..9 ] or sq[0, 10]
===>[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
To spare memory it’s possible to throw away every element after it was fetched:
sq.take!(1) => [1] sq.take!(1) => [4]
Of course it’s also possible to compute more complex lists like the Fibonacci sequence:
fib = LazyList.tabulate(0) { |x| x < 2 ? 1 : fib[x-2] + fib[x-1] }
fib[100] => 573147844013817084101
computes the 99th Fibonacci number. (We always start with index 0.)
fib[101] => 927372692193078999176
computes the 100th Fibonacci number. The already computed values are reused to compute this result. That’s a very transparent way to get memoization for sequences that require heavy computation.
You can also use the zip method to create fib:
fib = list(1, 1) { fib.zip(fib.drop) { |a, b| a + b } }
Another way to create the Fibonacci sequence with the build method is this:
fib = list(1, 1) { build { a + b }.where(:a => fib, :b => fib.drop(1)) }
You can create lazy lists that are based on arbitrary Enumerables, so can for example wrap your passwd file in one pretty easily:
pw = LazyList[ File.new("/etc/passwd") ]
Call grep to find the users root and flori: pw.grep /^(root|flori):/ => [“root:x:0:0:…n“,… ]
In this case the whole passwd file is slurped into the memory. If you use
pw.find { |x| x =~ /^root:/ } => "root:x:0:0:root:/root:/bin/bash\n"
instead, only every line until the root line is loaded into the memory.
To create more complex lazy lists, you can build them from already existing lazy lists.
Natural numbers:
naturals = LazyList.from(1)
Odd Numbers > 100:
odds = list { x }.where(:x => naturals) { x % 2 === 1 && x > 100 }
Alternative definition of square numbers:
squares = build { odds[0, x].inject(0) { |s, y| s + y } }.where :x => naturals
A very good introduction into lazy lists can be found in the scheme bible Structure and Interpretation of Computer Programs (SICP) [mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%25_sec_3.5]
Generated with the Darkfish Rdoc Generator 1.1.6.