1
\$\begingroup\$

I made a LazyList class that can wrap an iterable (list, generator etc.) and turn it into a MutableSequence (like list). This is great for when you need to both generate results lazily and cache them once generated - in my case it's because generating each value requires cloning a git repo, but the list of values is being passed to 3rd party code so I don't want to modify that to work with generators. Here's what I came up with...

First some imports and type definitions:

import functools
import itertools
from typing import (
    TYPE_CHECKING,
    Any,
    Callable,
    Generator,
    Generic,
    Hashable,
    Iterable,
    Iterator,
    MutableSequence,
    Optional,
    ParamSpec,
    Protocol,
    Sequence,
    Sized,
    SupportsIndex,
    TypeVar,
    cast,
    overload,
)


U = TypeVar("U", covariant=True)

class IterableAndSized(Protocol[U], Sized, Iterable[U]): ...

I don't really know why U has to be covariant here, it just does...

Now this is the main class LazyList[T] where T reflects the type of whatever iterable comes in. The iterable can also be sized - i.e. have __len__ defined - this allows lst[-5] to work without generating the whole list eagerly:

T = TypeVar("T")

# modified heavily from http://stupidpythonideas.blogspot.com/2014/07/lazy-python-lists.html
class LazyList(MutableSequence[T]):
    def __init__(self, iterable: Iterable[T] | IterableAndSized[T]):
        self._nonlazy: MutableSequence[T]
        self._lazy: Iterator[T]
        self._len = len(iterable) if isinstance(iterable, Sized) else None
        if isinstance(iterable, MutableSequence):
            self._nonlazy = iterable
            self._lazy = iter(())
        else:
            self._nonlazy = []
            self._lazy = iter(iterable)

    def __len__(self) -> int:
        if self._len is None:
            self._delazify()
            return len(self._nonlazy)
        return self._len

    @overload
    def _normalise_index(self, index: slice) -> slice: ...
    @overload
    def _normalise_index(self, index: SupportsIndex) -> int: ...

    def _normalise_index(self, index: slice | SupportsIndex) -> slice | int:
        "Convert -ve to +ve index - may delazify the entire list en-route"
        if isinstance(index, slice):
            return slice(
                0 if not index.start else self._normalise_index(index.start),
                len(self) if not index.stop else self._normalise_index(index.stop),
                index.step or 1,
            )
        else:
            return len(self) + idx if (idx := int(index)) < 0 else idx

    def _delazify(
        self, normalised_index: Optional[slice | SupportsIndex] = None
    ) -> None:
        if normalised_index is None:
            self._nonlazy.extend(self._lazy)  # hydrate whatever is left
        elif isinstance(normalised_index, slice):
            try:
                end_of_slice = range(
                    normalised_index.start, normalised_index.stop, normalised_index.step
                )[-1]
            except IndexError:
                pass  # range returned an empty array, so no need to populate further
            else:
                self._delazify(end_of_slice)
        elif (remainder := int(normalised_index) - len(self._nonlazy) + 1) < 0:
            pass  # that bit of list is already hydrated
        else:
            self._nonlazy.extend(itertools.islice(self._lazy, remainder))

    @overload
    def __getitem__(self, unsafe_index: SupportsIndex) -> T: ...
    @overload
    def __getitem__(self, unsafe_index: slice) -> MutableSequence[T]: ...

    def __getitem__(
        self, unsafe_index: SupportsIndex | slice
    ) -> T | MutableSequence[T]:
        normalised_index = self._normalise_index(unsafe_index)
        self._delazify(normalised_index)
        return self._nonlazy[normalised_index]

    def __delitem__(self, unsafe_index: SupportsIndex | slice) -> None:
        normalised_index = self._normalise_index(unsafe_index)
        self._delazify(normalised_index)
        del self._nonlazy[normalised_index]

    # fmt: off

    @overload
    def __setitem__(self, unsafe_index: SupportsIndex, value: T) -> None: ...
    @overload
    def __setitem__(self, unsafe_index: slice, value: Iterable[T]) -> None: ...
    # fmt: on

    def __setitem__(
        self, unsafe_index: SupportsIndex | slice, value: T | Iterable[T]
    ) -> None:
        normalised_index = self._normalise_index(unsafe_index)
        self._delazify(normalised_index)
        if not TYPE_CHECKING:  # see https://stackoverflow.com/questions/70247756/mypy-incompatible-types-error-when-one-overload-function-calls-another-in-setitem
            self._nonlazy[normalised_index] = value
        elif isinstance(normalised_index, slice):
            self._nonlazy[normalised_index] = cast(Iterable[T], value)
        else:
            self._nonlazy[normalised_index] = cast(T, value)

    def insert(self, unsafe_index: int, value: T) -> None:
        if unsafe_index:
            normalised_index = self._normalise_index(unsafe_index - 1)
            self._delazify(normalised_index)
        if self._len is not None:
            self._len += 1
        self._nonlazy.insert(normalised_index, value)

    def __iter__(self) -> Iterator[T]:
        yield from self._nonlazy
        for value in self._lazy:
            self._nonlazy.append(value)
            yield value

    def append(self, value: T) -> None:
        if self._len is not None:
            self._len += 1
        self._lazy = itertools.chain(self._lazy, (value,))

    def extend(self, values: Iterable[T] | IterableAndSized[T]) -> None:
        if self._len is not None:
            if isinstance(values, Sized):
                self._len += len(values)
            else:  # size is no longer known if we chain a random iterable
                self._len = None
        self._lazy = itertools.chain(self._lazy, values)

    def clear(self) -> None:
        self._len = 0
        self._nonlazy, self._lazy = [], iter(())

    def __str__(self) -> str:
        return "[{}]".format(
            ", ".join(itertools.chain(map(repr, self._nonlazy), ["..."]))
        )

    def __repr__(self) -> str:
        return f"LazyList({self})"

Finally I wrote some decorators for generator functions so they can work with lazy lists. Since generators don't have a length, -ve indexing would require eagerly generating the whole list to find the end and then step back. However the @sized decorator lets you specify a __len__ for the generator to make it work (see examples at the end). This is all tested with the mypy latest branch to support ParamSpec variables:

P = ParamSpec("P")

def lazylist(
    func: Callable[P, Iterable[T] | IterableAndSized[T]]
) -> Callable[P, LazyList[T]]:
    @functools.wraps(func)
    def wrapper(*args: P.args, **kwargs: P.kwargs) -> LazyList[T]:
        return LazyList(func(*args, **kwargs))

    return wrapper


class SizedGenerator(Generic[T]):
    def __init__(self, gen: Iterator[T], length: int):
        self.gen = gen
        self.length = length

    def __len__(self) -> int:
        return self.length

    def __iter__(self) -> Iterator[T]:
        return self.gen


def sized(
    length: int,
) -> Callable[[Callable[P, Iterator[T]]], Callable[P, IterableAndSized[T]]]:
    def _makesized(func: Callable[P, Iterator[T]]) -> Callable[P, IterableAndSized[T]]:
        @functools.wraps(func)
        def wrapper(*args: P.args, **kwargs: P.kwargs) -> IterableAndSized[T]:
            return SizedGenerator(func(*args, **kwargs), length)

        return wrapper

    return _makesized

Examples

@lazylist
@sized(10)
def sized_generator() -> Generator[int, None, None]:
    for i in range(10):
        print(f"Sized generated {i}")
        yield i


@lazylist
def unsized_generator() -> Generator[int, None, None]:
    for i in range(10):
        print(f"Unsized generated {i}")
        yield i


s = sized_generator()
print(f"{s[-3]=}")  # only generates up to 7
print(f"{s[:5]=}")  # doesn't generate any more values since we already have the first 5

u = unsized_generator()
print(f"{u[-3]=}")  # generates entire list
print(f"{u[:5]=}")  # doesn't generate any more values

Try it online!


Feedback

I'd love to hear anything, but some ideas:

  • Is this a stupid idea
  • Performance
  • Bugs and edge cases
  • Pythonicness
  • Type Safety
  • User Interface (I want this to be obvious to use if possible)

This code looks complicated but I'm actually a bit of a python beginner so anything would be good feedback. Made with python 3.10 and mypy bleeding edge pre-release for ParamSpec (you can experiment here), the TIO link is for 3.8 and is functionally equivalent.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ For something like only generates up to 7, what does your code do that itertools.islice does not? \$\endgroup\$
    – Reinderien
    Dec 13 '21 at 19:46
  • \$\begingroup\$ @Reinderien indeed this is built on islice to generate a subset of values on demand. But unlike islice, this fulfills the mutable sequence protocol so can be indexed or sliced like a regular list and use negative indices to generate some distance from the end. Also this caches values in a way that's a bit simpler than using tee. For example, if a is a lazy list, then a[5] generates up to index 5, a[7] generates only 6 and 7 and reuses the previous 5 values. Does that make sense? \$\endgroup\$
    – Greedo
    Dec 13 '21 at 19:57
  • \$\begingroup\$ It does, but.. I'd like to hear more about why this is used with your repo generation case to trust that it's justified. \$\endgroup\$
    – Reinderien
    Dec 13 '21 at 23:12
  • \$\begingroup\$ @Reinderien Good point, let me give some more details: I'm creating a package manager like pip where a git repo represents a package, and the repo contains a metadata file that specifies the version number of the package, and a list of dependencies + their compatible versions. Where this lazylist comes in is I'm using a library 'Mixology' to do automatic dependency resolution. For each package it expects a list of versions, most recent first, and their dependencies. However because this data is in the metadata file, I need to traverse the git history to obtain it... \$\endgroup\$
    – Greedo
    Dec 14 '21 at 15:29
  • \$\begingroup\$ ...which is slow as it requires checking out a commit and parsing the metadata file to get the version number + dependencies. The resolver starts from the most recent version of a package then works back until it finds a version that works with all the other packages - this doesn't require eagerly fetching all version metadata (hence the lazy part). Additionally, if 2 packages have the same dependency then this list of versions is re-used, so I also want to cache any work that's already been done in generating the list. The mixology code expects versions as a list so that's the api I've chosen \$\endgroup\$
    – Greedo
    Dec 14 '21 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.