This is a (python 3.0) recipe for LazyLists, or ordered sequences whose contents are generated lazily by an iterator.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | ```
"""Module for the creation and use of iterator-based lazy lists.
this module defines a class LazyList which can be used to represent sequences
of values generated lazily. One can also create recursively defined lazy lists
that generate their values based on ones previously generated."""
__author__ = 'Dan Spitz'
__all__ = ('LazyList', 'RecursiveLazyList', 'lazylist')
import itertools
import abc
class LazyList(metaclass = abc.ABCMeta):
"""A Sequence whose values are computed lazily by an iterator.
"""
def __init__(self, iterable):
self._exhausted = False
self._iterator = iter(iterable)
self._data = []
def __len__(self):
"""Get the length of a LazyList's computed data."""
return len(self._data)
def __getitem__(self, i):
"""Get an item from a LazyList.
i should be a positive integer or a slice object."""
if isinstance(i, int):
#index has not yet been yielded by iterator (or iterator exhausted
#before reaching that index)
if i >= len(self):
self.exhaust(i)
elif i < 0:
raise ValueError('cannot index LazyList with negative number')
return self._data[i]
#LazyList slices are iterators over a portion of the list.
elif isinstance(i, slice):
start, stop, step = i.start, i.stop, i.step
if any(x is not None and x < 0 for x in (start, stop, step)):
raise ValueError('cannot index or step through a LazyList with'
'a negative number')
#set start and step to their integer defaults if they are None.
if start is None:
start = 0
if step is None:
step = 1
def LazyListIterator():
count = start
predicate = ((lambda: True) if stop is None
else (lambda: count < stop))
while predicate():
try:
yield self[count]
#slices can go out of actual index range without raising an
#error
except IndexError:
break
count += step
return LazyListIterator()
raise TypeError('i must be an integer or slice')
def __iter__(self):
"""return an iterator over each value in the sequence,
whether it has been computed yet or not."""
return self[:]
def computed(self):
"""Return an iterator over the values in a LazyList that have
already been computed."""
return self[:len(self)]
def exhaust(self, index = None):
"""Exhaust the iterator generating this LazyList's values.
if index is None, this will exhaust the iterator completely.
Otherwise, it will iterate over the iterator until either the list
has a value for index or the iterator is exhausted.
"""
if self._exhausted:
return
if index is None:
ind_range = itertools.count(len(self))
else:
ind_range = range(len(self), index + 1)
for ind in ind_range:
try:
self._data.append(next(self._iterator))
except StopIteration: #iterator is fully exhausted
self._exhausted = True
break
class RecursiveLazyList(LazyList):
@abc.abstractmethod
def _producer(self):
"""generator method that yields the LazyList's contents"""
while False:
yield
def __init__(self, *args, **kwds):
super().__init__(self._producer(*args, **kwds))
def lazylist(producer):
"""Decorator for creating a RecursiveLazyList subclass.
This should decorate a generator function taking the LazyList object as its
first argument which yields the contents of the list in order.
"""
#ABCMeta is the metaclass of LazyList and its subclasses
return abc.ABCMeta(producer.__name__,
(RecursiveLazyList,),
dict(_producer = producer))
#two examples
if __name__ = '__main__':
#fibonnacci sequence in a lazy list.
@lazylist
def fibgen(lst):
yield 0
yield 1
for a, b in zip(lst, lst[1:]):
yield a + b
fibs = fibgen() #now fibs can be indexed or iterated over as if it were
#an infinitely long list containing the fibonnaci sequence
#prime numbers in a lazy list.
@lazylist
def primegen(lst):
yield 2
for candidate in itertools.count(3): #start at next number after 2
#if candidate is not divisible by any smaller prime numbers,
#it is a prime.
if all(candidate % p for p in lst.computed()):
yield candidate
primes = primegen() #same for primes- treat it like an infinitely long list
#containing all prime numbers.
print(fibs[0], fibs[1], fibs[2], primes[0], primes[1], primes[2])
print(list(fibs[:10]), list(primes[:10]))
``` |

For Python 3.0. A lazy list can be used for memoization of a function, and for more complicated things such as recursively defined sequences. Getting a slice of a LazyList returns an iterator, since I believe this is the best use of python's slicing syntax. As demonstrated in the fibs and primes examples, infinitely long LazyLists are possible. Please let me know of any ways to clean this up or improve it otherwise.

I suggest you to break the longer lines.

Done- now it should never be wider than 80 columns.

if you like the idea of dans lazy list, but want it in python 2.5, ive submitted a backport here