# RDoc Documentation

## 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 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 homepage of this library is located at

### 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
```

``` 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) [mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%25_sec_3.5]

## Methods

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.