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]                                                                        # needs sage.libs.pari
547
sage: P[10:34]                                                                      # needs sage.libs.pari
lazy list [31, 37, 41, ...]
sage: P[12:23].list()                                                               # needs sage.libs.pari
[41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83]

sage: f = lazy_list((i**2 - 3*i for i in range(10)))
sage: print(" ".join(str(i) for i in f))
0 -2 -2 0 4 10 18 28 40 54
sage: i1 = iter(f)
sage: i2 = iter(f)
sage: [next(i1), next(i1)]
[0, -2]
sage: [next(i2), next(i2)]
[0, -2]
sage: [next(i1), next(i2)]
[-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

You can easily create your own class inheriting from lazy_list_generic. You should call the lazy_list_generic constructor (optionally with some precomputed values for the cache) and implement the method _new_slice that returns a new chunk of data at each call. Here is an example of implementation of the Thue–Morse word that is obtained as the fixed point of the substitution \(0 \to 01\) and \(1 \to 10\):

sage: from sage.misc.lazy_list import lazy_list_generic
sage: class MyThueMorseWord(lazy_list_generic):
....:     def __init__(self):
....:         self.i = 1
....:         lazy_list_generic.__init__(self, cache=[0,1])
....:     def _new_slice(self):
....:         letter = self.get(self.i)
....:         self.i += 1
....:         return [0,1] if letter == 0 else [1,0]
sage: w = MyThueMorseWord()
sage: w
lazy list [0, 1, 1, ...]
sage: all(w[i] == ZZ(i).popcount()%2 for i in range(100))
True
sage: w[:500].list() == w[:1000:2].list()
True

Alternatively, you can create the lazy list from an update function:

sage: def thue_morse_update(values):
....:     n = len(values)
....:     if n == 0:
....:         letter = 0
....:     else:
....:         assert n%2 == 0
....:         letter = values[n//2]
....:     values.append(letter)
....:     values.append(1-letter)
sage: w2 = lazy_list(update_function=thue_morse_update)
sage: w2
lazy list [0, 1, 1, ...]
sage: w2[:500].list() == w[:500].list()
True

You can also create user-defined classes (Python) and extension types (Cython) inheriting from lazy_list_generic. In that case you would better implement directly the method _update_cache_up_to. See the examples in this file with the classes lazy_list_from_iterator and lazy_list_from_function.

Classes and Methods

sage.misc.lazy_list.lazy_list(data=None, initial_values=None, start=None, stop=None, step=None, update_function=None)

Return a lazy list.

INPUT:

• data – data to create a lazy list from. This can be

  1. a (possibly infinite) iterable,

  2. a function (that takes as input an integer n and return the n-th term of the list),

  3. or a standard Python container list or tuple.

• initial_values – the beginning of the sequence that will not be computed from the data provided.

• update_function – you can also construct a lazy list from a function that takes as input a list of precomputed values and updates it with some more values.

Note

If you want finer tuning of the constructor you can directly instantiate the classes associated to lazy lists that are lazy_list_generic, lazy_list_from_iterator, lazy_list_from_function.

EXAMPLES:

The basic construction of lazy lists.

sage: from sage.misc.lazy_list import lazy_list

1. Iterators:

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

2. Functions:

   sage: lazy_list(lambda n: (n**2)%17)
   lazy list [0, 1, 4, ...]
   

3. Plain lists:

   sage: lazy_list([1,5,7,2])
   lazy list [1, 5, 7, ...]
   

If a function is only defined for large values, you can provide the beginning of the sequence manually:

sage: l = lazy_list(divisors, [None])
sage: l
lazy list [None, [1], [1, 2], ...]

Lazy lists behave like lists except that they are immutable:

sage: l[3::5]
lazy list [[1, 3], [1, 2, 4, 8], [1, 13], ...]

If your lazy list is finite, you can obtain the underlying list with the method \(.list()\):

sage: l[30:50:5].list()
[[1, 2, 3, 5, 6, 10, 15, 30],
 [1, 5, 7, 35],
 [1, 2, 4, 5, 8, 10, 20, 40],
 [1, 3, 5, 9, 15, 45]]

sage.misc.lazy_list.lazy_list_formatter(L, name='lazy list', separator=', ', more='...', opening_delimiter='[', closing_delimiter=']', preview=3)

Return a string representation of L.

INPUT:

• L – an iterable object

• name – (default: 'lazy list') a string appearing at first position (i.e., in front of the actual values) in the representation

• opening_delimiter – (default: '[') a string heading the shown entries

• closing_delimiter – (default: ']') a string trailing the shown entries

• separator – (default: ', ') a string appearing between two entries

• more – (default: '...') a string indicating that not all entries of the list are shown

• preview – (default: 3) an integer specifying the number of elements shown in the representation string

OUTPUT:

A string.

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list_formatter
sage: lazy_list_formatter(srange(3, 1000, 5), name='list')
'list [3, 8, 13, ...]'

sage: # needs sage.libs.pari
sage: from sage.misc.lazy_list import lazy_list
sage: L = lazy_list(Primes()); L
lazy list [2, 3, 5, ...]
sage: repr(L) == lazy_list_formatter(L)
True
sage: lazy_list_formatter(L, name='primes')
'primes [2, 3, 5, ...]'
sage: lazy_list_formatter(L, opening_delimiter='(', closing_delimiter=')')
'lazy list (2, 3, 5, ...)'
sage: lazy_list_formatter(L, opening_delimiter='', closing_delimiter='')
'lazy list 2, 3, 5, ...'
sage: lazy_list_formatter(L, separator='--')
'lazy list [2--3--5--...]'
sage: lazy_list_formatter(L, more='and more')
'lazy list [2, 3, 5, and more]'
sage: lazy_list_formatter(L, preview=10)
'lazy list [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...]'
sage: lazy_list_formatter(L, name='primes',
....:                     opening_delimiter='', closing_delimiter='',
....:                     separator=' ', more='->', preview=7)
'primes 2 3 5 7 11 13 17 ->'

class sage.misc.lazy_list.lazy_list_from_function

Bases: lazy_list_generic

INPUT:

• function – a function that maps n to the element at position n. (This function only needs to be defined for length larger than the length of the cache.)

• cache – an optional list to be used as the cache. Be careful that there is no copy.

• stop – an optional integer to specify the length of this lazy list. (Otherwise it is considered infinite).

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list_from_function
sage: lazy_list_from_function(euler_phi)                                    # needs sage.libs.pari
lazy list [0, 1, 1, ...]
sage: lazy_list_from_function(divisors, [None])
lazy list [None, [1], [1, 2], ...]

class sage.misc.lazy_list.lazy_list_from_iterator

Bases: lazy_list_generic

Lazy list built from an iterator.

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())[8:20551:2]
sage: m2
lazy list [8, 10, 12, ...]

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

class sage.misc.lazy_list.lazy_list_from_update_function

Bases: lazy_list_generic

INPUT:

• function – a function that updates a list of precomputed values. The update function should take as input a list and make it longer (using either the methods append or extend). If after a call to the update function the list of values is shorter a RuntimeError will occurr. If no value is added then the lazy list is considered finite.

• cache – an optional list to be used as the cache. Be careful that there is no copy.

• stop – an optional integer to specify the length of this lazy list (otherwise it is considered infinite)

class sage.misc.lazy_list.lazy_list_generic

Bases: object

A lazy list

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: l = lazy_list(Primes())
sage: l                                                                         # needs sage.libs.pari
lazy list [2, 3, 5, ...]
sage: l[200]                                                                    # needs sage.libs.pari
1229

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: unable to convert rational 1/2 to an integer

list()

Return the list made of the elements of self.

Note

If the iterator is sufficiently large, this will build a list of length PY_SSIZE_T_MAX which should be beyond the capacity of your RAM!

EXAMPLES:

sage: from sage.misc.lazy_list import lazy_list
sage: P = lazy_list(Primes())
sage: P[2:143:5].list()                                                     # needs sage.libs.pari
[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]

sage.misc.lazy_list.slice_unpickle(master, start, stop, step)

Unpickle helper