lazy evaluation in Python

[Bryn Keller]

Fernando Rodriguez wrote:

> Hi!
>
>     What's the best way to implement lazy evaluation (streams or lazy lists)
> in Python? O:-)
> TIA

This is a tricky question that I debated for some time over on
comp.lang.functional, where people would say 'Python can't do lazy stuff', and
I'd show them it could, and then they'd say 'But it can't do xyz kind of lazy
stuff', and I'd show them it could again. Unfortunately, since there is no
language support for laziness, nor any standard module for it, it tends to be
ad-hoc stuff that solves one particular problem. I'm working on a general
purpose lazy module for python now, I hope to have something for public
consumption in a couple of weeks.

In the meantime, here's a little of what I'm talking about with regards to
ad-hoc solutions that may solve your particular problem, copied from the
discussion on c.l.functional:

<quote>

> In your code example, you return the result of the index - which does not
> seem to be related to laziness in any way.
>
> The simplest example (in Haskell) would be this:
>
>   ones = 1 : ones
>
> This is the infinite list of ones.

class Ones:
    def __getitem__(self, i):
        return 1

>
>
> More interesting, the natural numbers:
>
>   nats_from n = n : nats_from n + 1
>   nats = nats_from 1
>
> This is probably what you intended.

class NatsFrom:
    def __init__(self, start):
        self.start = start
    def __getitem__(self, i):
        return self.start + i

>
>
> But try something like the following with your definition:
>
>   evens = map (* 2) nats

Aha! Now this is a little different. We can of course get the effect, though if
we make
the list returned apply the mapping lazily instead:

class lazymap:
    def __init__(self, mapfunc, list):
        self._mapfunc = mapfunc
        self._underlying = list
    def __getitem__(self, i):
        return self._mapfunc(self._underlying[i])
    def __repr__(self):
        return "[" + str(self[0]) + ", " + str(self[1]) + "..]

evens = lazymap(lambda x:x * 2, nats)



>
>
> This will quickly show you that your definition is much more eager than
> intended... (non-termination).
>
> Whereas in Haskell you can easily write:
>
>   take 10 evens
>
> to get the first 10 even numbers.

Okay for this we either have to write a loop or add slicing support to NatsFrom
and
lazymap:

class NatsFrom:
    def __init__(self, start):
        self.start = start
    def __getitem__(self, i):
        return self.start + i

    def __getslice__(self, i, j):
        lst = []
        for num in range(i, j):
            lst.append(num)


class lazymap:
    def __init__(self, mapfunc, list):
        self._mapfunc = mapfunc
        self._underlying = list
    def __getitem__(self, i):
        return self._mapfunc(self._underlying[i])

    def __getslice__(self, i, j):
        lst = []
        for num in range(i,j):
            lst.append(self[num])
        return lst

    def __repr__(self):
        return "[" + str(self[0]) + ", " + str(self[1]) + "..]"

nats = NatsFrom(1)

evens = lazymap(lambda x:x * 2, nats)

now evens[:10] (equivalent to take 10 evens) is:
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

>
>
> If you want to see a more "heavy-weight" example of laziness, you can try
> this (also uses a list comprehension):
>
>   primes = sieve [2..]
>   sieve (h:t) = h : sieve [x| x<-t, x`mod`h /= 0]
>
> Writing "take 10 primes" yields: [2,3,5,7,11,13,17,19,23,29]

Okay, this is a bit meatier! I have most of a solution, but I don't have time to
finish
it now. I'll send it next week.

>
>
> And of course, you can again "map", "zip" and whatever you like to do with
> the list... - because it is lazy.

Sure. We couldn't use the python builtins for mapping and zipping and so on, but
we
could make lazy versions like we've seen above.

</quote>

One interesting question I've run  into in trying to create a general-purpose
lazy tuple class is slicing. In python, if you write foo[3:], what gets sent to
__getslice__ is 3, sys.max_int. What will happen to that when Python supports
longs as sequence indices?


Bryn