Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 138 lines
  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.

3 comments

bearophile - 15 years, 9 months ago  # | flag

I suggest you to break the longer lines.

Dan Spitz (author) 15 years, 9 months ago  # | flag

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

Michael Pust 15 years, 8 months ago  # | flag

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

Created by Dan Spitz on Fri, 8 Aug 2008 (MIT)
Python recipes (4591)
Dan Spitz's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks