# Lazy lists¶

Lazy lists

A lazy list is an iterator that behaves like a list and possesses a cache mechanism. A lazy list is potentially infinite and speed performances of the cache is comparable with Python lists. One major difference with original Python list is that lazy list are immutable. The advantage is that slices share memory.

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: P = lazy_list(Primes())
sage: P[100]
547
sage: P[10:34]
lazy list [31, 37, 41, ...]
sage: P[12:23].list()
[41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83]

sage: f = lazy_list((i**2-3*i for i in xrange(10)))
sage: for i in f: print i,
0 -2 -2 0 4 10 18 28 40 54
sage: i1 = iter(f)
sage: i2 = iter(f)
sage: print i1.next(), i1.next()
0 -2
sage: print i2.next(), i2.next()
0 -2
sage: print i1.next(), i2.next()
-2 -2


It is possible to prepend a list to a lazy list:

sage: from itertools import count
sage: l = [3,7] + lazy_list(i**2 for i in count())
sage: l
lazy list [3, 7, 0, ...]


But, naturally, not the other way around:

sage: lazy_list(i-1 for i in count()) + [3,2,5]
Traceback (most recent call last):
...
TypeError: can only add list to lazy_list

class sage.misc.lazy_list.lazy_list

Bases: object

Lazy list.

INPUT:

• iterator – an iterable or an iterator
• cacheNone (default) or a list - used to initialize the cache.
• start, stop, stepNone (default) or a non-negative integer - parameters for slices

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: from itertools import count
sage: m = lazy_list(count()); m
lazy list [0, 1, 2, ...]

sage: m2 = lazy_list(count(), start=8, stop=20551, step=2)
sage: m2
lazy list [8, 10, 12, ...]

sage: x = iter(m)
sage: print x.next(), x.next(), x.next()
0 1 2
sage: y = iter(m)
sage: print y.next(), y.next(), y.next()
0 1 2
sage: print x.next(), y.next()
3 3
lazy list [0, 1, 2, ...]


Note

• lazy_list interprets the constant (size_t)-1 as infinity
• all entry indices are stictly less than stop so that lazy_list agrees with range(start, stop)
get(i)

Return the element at position i.

If the index is not an integer, then raise a TypeError. If the argument is negative then raise a ValueError. Finally, if the argument is beyond the size of that lazy list it raises a IndexError.

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: from itertools import chain, repeat
sage: f = lazy_list(chain(iter([1,2,3]), repeat('a')))
sage: f.get(0)
1
sage: f.get(3)
'a'
sage: f.get(0)
1
sage: f.get(4)
'a'

sage: g = f[:10]
sage: g.get(5)
'a'
sage: g.get(10)
Traceback (most recent call last):
...
IndexError: lazy list index out of range
sage: g.get(1/2)
Traceback (most recent call last):
...
TypeError: rational is not an integer

info()

Print information about self on standard output.

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: P = lazy_list(iter(Primes()))[10:21474838:4]
sage: P.info()
cache length 0
start        10
stop         21474838
step         4
sage: P[0]
31
sage: P.info()
cache length 11
start        10
stop         21474838
step         4

list()

Return the list made of the elements of self.

Note

If the iterator is sufficiently large, this will build a list of length (size_t)-1 which should be beyond the capacity of your RAM!

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: P = lazy_list(iter(Primes()))
sage: P[2:143:5].list()
[5, 19, 41, 61, 83, 107, 137, 163, 191, 223, 241, 271, 307, 337, 367, 397, 431, 457, 487, 521, 563, 593, 617, 647, 677, 719, 751, 787, 823]
sage: P = lazy_list(iter([1,2,3]))
sage: P.list()
[1, 2, 3]
sage: P[:100000].list()
[1, 2, 3]
sage: P[1:7:2].list()
[2]


TESTS:

Check that the cache is immutable:

sage: lazy = lazy_list(iter(Primes()))[:5]
sage: l = lazy.list(); l
[2, 3, 5, 7, 11]
sage: l[0] = -1; l
[-1, 3, 5, 7, 11]
sage: lazy.list()
[2, 3, 5, 7, 11]

start_stop_step()

Return the triple (start, stop, step) of reference points of the original lazy list.

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: p = lazy_list(iter(Primes()))[:2147483647]
sage: p.start_stop_step()
(0, 2147483647, 1)
sage: q = p[100:1042233:12]
sage: q.start_stop_step()
(100, 1042240, 12)
sage: r = q[233::3]
sage: r.start_stop_step()
(2896, 1042252, 36)
sage: 1042241%3 == 233%3
True

class sage.misc.lazy_list.lazy_list_iterator

Bases: object

Iterator for a lazy list.

INPUT:

• l – a lazy list
• pos – (Default: None) None or a non-negative integer specifying the starting position
next()

x.next() -> the next value, or raise StopIteration

class sage.misc.lazy_list.stopped_lazy_list_iterator

Bases: object

A lazy list iterator which eventually stops.

INPUT:

• l – a lazy list
• pos – (Default: None) None or a non-negative integer specifying the starting position
next()

x.next() -> the next value, or raise StopIteration

Decorators

#### Next topic

Class inheritance graphs