An implementation of singly linked lists with lazy expansion of iterators/iterables

lazychain.py

from typing import TypeVar, Generic
from collections.abc import Iterable

T = TypeVar('T')

class Chain(Generic[T]):

    # Implementation note: the _back field is used to represent different 
    # states of the chain. This implementation technique, borrowed from the
    # implementation of dynamic lists in Poplog, requires only 2 fields and
    # has the advantage of overwriting unwanted references to the iterator, 
    # which therefore is released as soon as the chain is fully expanded.
    #
    #   True - this is an unexpanded node with the _front being the iterator
    #   False - this is an expanded _empty_ node, the front is ignored
    #   Chain - this is an expended _nonempty_ node, the front is the value
    #
    # It is an key fact that after bool(mychain) tests positive, it is safe to 
    # use _front/_back as synonyms for head()/tail(). Within the class this is 
    # used pervasively to avoid the overhead of a method call.

    def __init__( self, head: T, tail: Chain[T] ):
        """Private constructor
        :meta private:
        """
        self._front = head
        self._back = tail

    def __bool__( self ) -> bool:
        """
        True if the chain has any members, otherwise False. Will expand
        this chain node if required.
        """
        if self._back is True:
            try:
                item = next( self._front )
                c = Chain( self._front, True )
                self._front = item
                self._back = c
            except StopIteration:
                self._back = False
                self._front = None
        return self._back is not False
        
    def head( self ) -> T:
        """
        Returns the first item in the chain.
        """
        if self:
            return self._front
        else:
            raise Exception()

    def tail( self ) -> T:
        """
        Returns the chain that represents all but the first item. Chains
        form singly linked lists, so this is a fast operation that always
        yields the identical object.
        """
        if self:
            return self._back
        else:
            raise Exception()

    def new( self, x: T ) -> Chain[T]:
        """
        Allocates a new chain node with x as its head and the current chain
        as its tail.
        """
        return Chain( x, self )

    def __iter__( self ):
        """
        Returns an iterator over all the items in the chain. This will 
        gradually expand the underlying chain.
        """
        _chain = self
        while _chain:
            yield _chain._front
            _chain = _chain._back

    def __len__( self ) -> int:
        """
        Returns a count of the number of items in a chain, which also forces
        the expansion of the whole chain. If the chain is infinite this will
        not terminate!
        """
        c = self
        n = 0
        while c:
            n += 1
            c = c._back
        return n

    def expand( self ):
        """
        Force the expansion of the chain. 
        """
        c = self
        while c:
            c = c._back
        return self

    def __add__( self, it: Iterable[T] ) -> Chain[T]:
        """
        Construct a new chain that consists of the concatenation of all the
        items in self followed by all the items from it. Note that self is
        expanded but the supplied iterable/iterator is not.
        """
        if not isinstance( it, Chain ):
            it = Chain( iter(it), True )
        c = self
        r = Chain( None, False )
        while c:
            r = Chain( c._front, r )
            c = c._back
        while r:
            it = Chain( r._front, it )
            r = r._back
        return it

    def __repr__( self ):
        return f"chain([{','.join(map(repr,self))}])"

"""
We commonly construct empty chains, which are immutable. So we can (and should) 
share a single empty chain where possible. NIL points the value we reuse.
"""
NIL = Chain( None, False )

def lazychain( it:Iterable[T]=() ):
    """
    Returns an unexpanded chain based on the iterable/iterator. Using this
    constructor allows you to work with very large or even infinite chains.
    Note that because this is lazy, subsequent changes to the underlying 
    iterable maybe incorporated into the chain.
    """
    if it is ():
        return NIL
    return Chain( iter(it), True )

def chain( it:Iterable[T]=() ):
    """
    Returns a fully expanded chain based on the iterable/iterator. This is 
    useful when you need the chain to be independent of changes in the 
    underlying iterable.
    """
    if it is ():
        return NIL
    return lazychain( it ).expand()