[Python-ideas] lazy tuple unpacking

[Andrew Barnert]

> On Tuesday, July 8, 2014 9:18 AM, Paul Tagliamonte <paultag at gmail.com> wrote:



> Yeah, I think all the productive ideas (thanks, Andrew and Todd) to make
> this happen are mostly starting to converge on full-blown lazy lists,
> which is to say, generators which are indexable, sliceable, and work from both
> ends (which is to say: more than the current iterator protocol).


I don't think that's necessarily true.

First, I think the idea of just trying to index and slice the iterable and falling back to the current behavior is at least worth thinking about. It wouldn't solve the problem for iterators, but it would for your example (range), or any other kind of sequence that knows how to slice itself in a better way than making a list.

And to take that farther, you don't necessarily need to replace iterators with lazy lists, just with some kind of sequence. A view is just as indexable, sliceable, and reusable as a lazy list, and better in many ways, and Python already has views like dict_keys built in, and NumPy already uses a similar idea for slicing.

I believe either Guido or Nick has a writeup somewhere on why list slices being new lists rather than views is a good thing, not just a historical accident we're stuck with. But that doesn't mean that having views for many of the cases we use iterators for today (including a view comprehension, a viewtools library, etc.) would necessarily be a bad idea.

And, as I mentioned, expanding the notion of sequence to include weaker notions of bidirectional-only sequence and forward-only sequence eliminates many of the other need for iterators (but not all—a general generator function obviously can't return a reusable forward-only sequence).

If you're interest in more on this, see http://stupidpythonideas.blogspot.com/2014/07/lazy-tuple-unpacking.html and http://stupidpythonideas.blogspot.com/2014/07/swift-style-map-and-filter-views.html for some ideas.


> I totally like the idea, not sure how keen everyone will be about it.

> 
> I'm not sure I have the energy or drive to try and convince everyone on
> python-dev this is a good idea, but I'd totally love to play around
> with this. Anyone else?


Before trying to convince anyone this is a good idea, first you want to build a lazy-list library: a lazy list type, lazy-list versions of map/filter/dropwhile, etc.

It's actually pretty simple. A lazy list basically looks like this:

    class LazyList(collections.abc.Sequence):
        def __init__(self, iterable):
            self.lst, self.it = [], iter(iterable)
        def __getitem__(self, index):
            while index >= len(self.lst):
                self.lst.append(next(self.it))
            return self.lst[index]

You have to add slice support, set/del, etc., but it's all pretty simply. The only tricky question is what to do about slicing, because you have a choice there. You could just loop over the slice and get/set/del each index, or you could return a new LazyList around islice(self), or you could do the latter if stop is None else the former.

And then all the lazy functions just call the iterator function and wrap the result in a LazyList.

The big problem with lazy lists is that once a value is instantiated, it stays around as long as the list does. So, if you use a lazy list as an iterable, you're basically building the whole list in memory. Iterators obviously don't have that problem.


It's worth looking at Haskell and other lazy functional languages to see why they don't have that problem. Their lists are conses (singly-linked lists with tail sharing). So, making it lazy automatically means that if you just iterate L without keeping a reference, only one cons is around at a time, while if you keep a reference to L, the whole list is available in memory. That won't work for array-based lists like Python's, and I'm not sure how you'd solve that without completely changing the way iteration works in Python. (Of course you can easily implement cons lists in Python, and then make them lazy, but then they're not sequences—in particular, they're not indexable, and generally won't work with any typical Python algorithms that aren't already happy with iterators.)