== LazyList - Implementation of lazy lists for Ruby === Description 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. === Author Florian Frank mailto:flori@ping.de === License 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 === Download The latest version of this library can be downloaded at * http://rubyforge.org/frs?group_id=394 The homepage of this library is located at * http://lazylist.rubyforge.org === Example To compute the square numbers with a lazy list you can define one as 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 === References A very good introduction into lazy lists can be found in the scheme bible Structure and Interpretation of Computer Programs (SICP) [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%25_sec_3.5]