# -*- coding: utf-8 -*-

"""Cons and friends.

Hashable, pickleable, hooks into the built-in reversed(), can print like in Lisps.

"""

from abc import ABCMeta, abstractmethod

from collections.abc import Iterable, Iterator

from itertools import zip_longest

from .fun import composer1i

from .fold import foldr, foldl

from .it import rev

from .singleton import Singleton

# from .symbol import gensym

# explicit list better for tooling support

_exports = ["cons", "nil",

"LinkedListIterator", "LinkedListOrCellIterator", "TailIterator",

"BinaryTreeIterator", "ConsIterator",

"car", "cdr",

"caar", "cadr", "cdar", "cddr",

"caaar", "caadr", "cadar", "caddr", "cdaar", "cdadr", "cddar", "cdddr",

"caaaar", "caaadr", "caadar", "caaddr", "cadaar", "cadadr", "caddar", "cadddr",

"cdaaar", "cdaadr", "cdadar", "cdaddr", "cddaar", "cddadr", "cdddar", "cddddr",

"ll", "llist", "lreverse", "lappend", "lzip"]

#from itertools import product, repeat

#_ads = lambda n: product(*repeat("ad", n))

#_c2r = ["c{}{}r".format(*x) for x in _ads(2)]

#_c3r = ["c{}{}{}r".format(*x) for x in _ads(3)]

#_c4r = ["c{}{}{}{}r".format(*x) for x in _ads(4)]

#_exports.extend(_c2r)

#_exports.extend(_c3r)

#_exports.extend(_c4r)

__all__ = _exports

class Nil(Singleton):

"""The empty linked list. Singleton."""

# support the iterator protocol so we can say tuple(nil) --> ()

def __iter__(self):

return self

def __next__(self):

raise StopIteration()

def __repr__(self):

return "nil"

nil = Nil()

class ConsIterator(metaclass=ABCMeta):

"""Abstract base class for iterators operating on cons cells.

Can be used to define your own walking strategies for custom structures

built out of cons cells.

``startcell`` is the cons cell to start in (will be checked it is a cons),

and ``walker`` is a generator function (i.e. not started yet) that yields

the data in the desired order.

Basically all a derived class needs to do is define a walker and then call

``super().__init__(startcell, walker)``.

For usage examples see the predefined iterators in ``unpythonic.llist``.

"""

@abstractmethod

def __init__(self, startcell, walker):

if not isinstance(startcell, cons):

raise TypeError(f"Expected a cons, got {type(startcell)} with value {startcell}")

self.walker = iter(walker(startcell)) # iter() needed to support gtrampolined generators

def __iter__(self):

return self

def __next__(self):

return next(self.walker)

Iterable.register(ConsIterator)

Iterator.register(ConsIterator)

class LinkedListIterator(ConsIterator):

"""Iterator for linked lists built from cons cells."""

def __init__(self, head, _fullerror=True):

def walker(head):

cell = head

while cell is not nil:

yield cell.car

if isinstance(cell.cdr, cons) or cell.cdr is nil:

cell = cell.cdr

else:

if _fullerror:

raise TypeError(f"Not a linked list: {head}")

else: # avoid infinite loop in cons.__repr__

raise TypeError("Not a linked list")

super().__init__(head, walker)

class LinkedListReverseIterator(LinkedListIterator):

"""Iterator for walking a linked list backwards.

Computes the reversed list at init time, so it can then be walked forward.

Cost O(n).

"""

def __init__(self, head, _fullerror=True):

self._data = lreverse(head)

super().__init__(self._data, _fullerror)

class LinkedListOrCellIterator(ConsIterator):

"""Like LinkedListIterator, but allow also a single cons cell.

Default iteration strategy. Useful for sequence unpacking of cons and ll.

"""

def __init__(self, head, _fullerror=True):

def walker(head):

cell = head

while cell is not nil:

yield cell.car

if isinstance(cell.cdr, cons) or cell.cdr is nil:

cell = cell.cdr

elif cell is head:

yield cell.cdr

break

else:

if _fullerror:

raise TypeError(f"Not a linked list or a single cons cell: {head}")

else: # avoid infinite loop in cons.__repr__ (it uses LinkedListIterator, though) # pragma: no cover

raise TypeError("Not a linked list or a single cons cell")

super().__init__(head, walker)

class TailIterator(ConsIterator): # for member()

"""Like LinkedListIterator, but yield successive tails (cdr, cddr, ...).

Example::

TailIterator(ll(1, 2, 3)) --> ll(1, 2, 3), ll(2, 3), ll(3)

"""

def __init__(self, head):

def walker(head):

cell = head

while cell is not nil:

yield cell # tail of list from this cell on

if isinstance(cell.cdr, cons) or cell.cdr is nil:

cell = cell.cdr

else:

raise TypeError(f"Not a linked list: {head}")

super().__init__(head, walker)

class BinaryTreeIterator(ConsIterator):

"""Iterator for binary trees built from cons cells."""

def __init__(self, root):

# def walker(cell): # FP, call stack overflow for deep trees

# for x in (cell.car, cell.cdr):

# if isinstance(x, cons):

# yield from walker(x)

# else:

# yield x

def walker(cell): # imperative, no call stack overflow (we keep our own data stack instead)

stack = [cell]

while stack:

cell = stack.pop()

a, d = cell.car, cell.cdr

ac, dc = isinstance(a, cons), isinstance(d, cons)

if not ac:

yield a

if not dc:

yield d

if dc:

stack.append(d)

if ac:

stack.append(a) # LIFO

super().__init__(root, walker)

class JackOfAllTradesIterator(ConsIterator):

"""Iterator that supports both binary trees and linked lists.

**CAUTION**: *jack of all trades*, because:

- To handle trees correctly, this iterator descends into any cons cell

contained in the input, **also in the car half**. This implies that

**nested linked lists will be flattened**.

- To handle list termination correctly, whenever the **cdr half**

contains a ``nil``, it will be omitted from the output. This implies

that for a tree which contains ``nil`` entries, **some** of those

``nil`` may be missing from the output.

If you want the ace for a particular trade, use the specific iterator for

the specific kind of cons structure you have.

"""

def __init__(self, root):

# @gtrampolined

# def walker(cell): # FP, tail-recursive in the cdr half only

# if isinstance(cell.car, cons):

# yield from walker(cell.car)

# else:

# yield cell.car

# if isinstance(cell.cdr, cons):

# return walker(cell.cdr) # signal gtrampolined to tail-chain

# elif cell.cdr is not nil:

# yield cell.cdr

def walker(cell):

stack = [cell]

while stack:

cell = stack.pop()

a, d = cell.car, cell.cdr

ac, dc = isinstance(a, cons), isinstance(d, cons)

if not ac:

yield a

if not dc and d is not nil:

yield d

if dc:

stack.append(d)

if ac:

stack.append(a) # LIFO

super().__init__(root, walker)

class cons:

"""Cons cell a.k.a. pair. Immutable, like in Racket.

Iterable. Default is to iterate as a linked list.

"""

def __init__(self, v1, v2):

self.car = v1

self.cdr = v2

self._immutable = True

def __setattr__(self, k, v):

if hasattr(self, "_immutable"):

raise TypeError("'cons' object does not support item assignment")

super().__setattr__(k, v)

def __iter__(self):

"""Return iterator with default iteration scheme: single cell or list."""

return LinkedListOrCellIterator(self)

def __reversed__(self):

"""For lists. Caution: O(n), works by building a reversed list."""

return LinkedListReverseIterator(self)

def __repr__(self):

"""Representation in pythonic notation.

Suitable for ``eval`` if all elements are."""

try: # duck test linked list (true list only, no single-cell pair)

# listcomp, not genexpr, since we want to trigger any exceptions **now**.

result_list = [repr(x) for x in LinkedListIterator(self, _fullerror=False)]

result_str = ", ".join(result_list)

return f"ll({result_str})"

except TypeError:

result_list = (repr(self.car), repr(self.cdr))

result_str = ", ".join(result_list)

return f"cons({result_str})"

def lispyrepr(self): # TODO: maybe rename or alias this to `__str__`?

"""Representation in Lisp-like dot notation."""

try:

result_list = [repr(x) for x in LinkedListIterator(self, _fullerror=False)]

except TypeError:

r = lambda obj: obj.lispyrepr() if hasattr(obj, "lispyrepr") else repr(obj)

result_list = (r(self.car), ".", r(self.cdr))

result_str = " ".join(result_list)

return f"({result_str})"

def __eq__(self, other):

if other is self:

return True

if isinstance(other, cons):

try: # duck test linked lists

ia, ib = (LinkedListIterator(x) for x in (self, other))

fill = object() # gensym("fill"), but object() is much faster, and we don't need a label, or pickle support.

for a, b in zip_longest(ia, ib, fillvalue=fill):

if a != b:

return False

return True

except TypeError:

return self.car == other.car and self.cdr == other.cdr

return False

def __hash__(self):

try: # duck test linked list

tpl = tuple(LinkedListIterator(self))

except TypeError:

tpl = (self.car, self.cdr)

return hash(tpl)

def _car(x):

return _typecheck(x).car

def _cdr(x):

return _typecheck(x).cdr

def _typecheck(x):

if not isinstance(x, cons):

raise TypeError(f"Expected a cons, got {type(x)} with value {x}")

return x

def _build_accessor(name):

spec = name[1:-1]

f = {'a': _car, 'd': _cdr}

return composer1i(f[char] for char in spec)

def car(x):

"""Return the first half of a cons cell."""

return _car(x)

def cdr(x):

"""Return the second half of a cons cell."""

return _cdr(x)

caar = _build_accessor("caar")

cadr = _build_accessor("cadr")

cdar = _build_accessor("cdar")

cddr = _build_accessor("cddr")

caaar = _build_accessor("caaar")

caadr = _build_accessor("caadr")

cadar = _build_accessor("cadar") # look, it's Darth Cadar!

caddr = _build_accessor("caddr")

cdaar = _build_accessor("cdaar")

cdadr = _build_accessor("cdadr")

cddar = _build_accessor("cddar")

cdddr = _build_accessor("cdddr")

caaaar = _build_accessor("caaaar")

caaadr = _build_accessor("caaadr")

caadar = _build_accessor("caadar")

caaddr = _build_accessor("caaddr")

cadaar = _build_accessor("cadaar")

cadadr = _build_accessor("cadadr")

caddar = _build_accessor("caddar")

cadddr = _build_accessor("cadddr")

cdaaar = _build_accessor("cdaaar")

cdaadr = _build_accessor("cdaadr")

cdadar = _build_accessor("cdadar")

cdaddr = _build_accessor("cdaddr")

cddaar = _build_accessor("cddaar")

cddadr = _build_accessor("cddadr")

cdddar = _build_accessor("cdddar")

cddddr = _build_accessor("cddddr")

def ll(*elts):

"""Make a linked list with the given elements.

``ll(...)`` plays the same role as ``[...]`` or ``(...)`` for lists or tuples,

respectively, but for linked lists. See also ``llist``.

**NOTE**: The returned data type is ``cons``, there is no ``ll`` type.

A linked list is just one kind of structure that can be built out of cons cells.

Equivalent to ``(list ...)`` in Lisps. Since in Python the name ``list``

refers to the builtin dynamic array type, we use the name ``ll``.

"""

return llist(elts)

def llist(iterable):

"""Make a linked list from iterable.

``llist(...)`` plays the same role as ``list(...)`` or ``tuple(...)`` for

lists or tuples, respectively, but for linked lists. See also ``ll``.

**NOTE**: The returned data type is ``cons``, there is no ``llist`` type.

A linked list is just one kind of structure that can be built out of cons cells.

**Efficiency**:

Because cons appends to the front, this is efficient for:

- ``reversed(some_linked_list)``, by just returning the already computed

reversed list that is internally stored by the reverse-iterator.

- Sequences, since they can be walked backwards; a linear walk is enough.

For a general iterable input, this costs a linear walk (forwards),

plus an ``lreverse``.

"""

if isinstance(iterable, LinkedListReverseIterator):

# avoid two extra reverses by reusing the internal data.

return iterable._data

return lreverse(rev(iterable))

def lreverse(iterable):

"""Reverse an iterable, loading the result into a linked list.

If you have a linked list and want an iterator instead, use ``reversed(l)``.

The computational cost is the same in both cases, O(n).

"""

return foldl(cons, nil, iterable)

def lappend(*ls):

"""Append the given linked lists left-to-right."""

def lappend_two(l1, l2):

return foldr(cons, l2, l1)

return foldr(lappend_two, nil, ls)

def member(x, l):

"""Walk linked list l and check if item x is in it.

Returns:

The matching cons cell (tail of l) if x was found; False if not.

"""

for t in TailIterator(l):

if t.car == x:

return t

return False

def lzip(*ls):

"""Zip linked lists, producing a linked list of linked lists.

Built-in zip() works too, but produces tuples.

"""

return llist(map(ll, *ls))