# Handy functional-style lists and dicts.

def is_list_of(lst, typ):
    return isinstance(lst, BaseList) and lst.is_list_of(typ)

def as_cons_list(lst):
    if isinstance(lst, BaseList): return lst
    return ConsList.from_iterable(lst)

class BaseList(object):
    def with_hd(self, hd):
        return ConsList(hd, self)

    def with_key_value(self, key, value):
        return AssocList(key, value, self)

    def as_list(self):
        return list(self)

    def is_len(self, exp_cnt):
        "Returns true if len(self) == exp_cnt.  Takes O(exp_cnt) time."
        cnt = 0
        for item in self:
            if cnt == exp_cnt:
                return False
            cnt += 1
        return cnt == exp_cnt
            
    def __cmp__(self, other):
        if isinstance(other, (list, tuple)):
            return cmp(self.as_list(), other)
        assert isinstance(other, BaseList)
        return self._cmp(other)

    def __iter__(self):
        ptr = self
        while ptr:
            yield ptr.hd
            ptr = ptr.tl

    def fold_left(self, func, initial):
        res = initial
        for item in self:
            res = func(res, item)
        return res

    @classmethod
    def from_iterable(cls, lst):
        return cls.from_iterator(iter(lst))
    
    @classmethod
    def from_iterator(cls, iter):
        try:
            hd = iter.next()
            tl = cls.from_iterable(iter)
            return cls(hd, tl)
        except StopIteration:
            return cls.EMPTY

class _EmptyList(BaseList):
    def __add__(self, other):
        assert isinstance(other, BaseList)
        return other

    def _cmp(self, other):
        if self is other:
            return 0
        return -1
    
    def __nonzero__(self):
        return False
    
    def __len__(self):
        return 0

    def __getitem__(self, key):
        raise KeyError(key)

    def __repr__(self):
        return "[]"
    
    def is_list_of(self, type):
        return True
    
    def map(self, func):
        return self
    
    def filter(self, func):
        return self

BaseList.EMPTY = _EmptyList()

class ConsList(BaseList):
    def __init__(self, hd, tl=BaseList.EMPTY):
        assert tl is not None   # (use self.EMPTY, not None)
        self.hd = hd
        self.tl = tl

    def _cmp(self, other):
        if self is other:
            return 0
        if other is ConsList.EMPTY:
            return 1
        c = cmp(self.hd, other.hd)
        if c:
            return c
        return self.tl._cmp(other.tl)
    
    def __add__(self, other):
        assert isinstance(other, BaseList)
        return (self.tl + other).with_hd(self.hd)

    def __nonzero__(self):
        return True

    def __len__(self):
        cnt = 0
        for _ in self:
            cnt += 1
        return cnt

    def __repr__(self):
        return repr(self.as_list())
    
    def is_list_of(self, type):
        """ Checks if this is a list of 'type' elements.  Assumes (but
        does not check) that all items in the list are of the same
        type. """
        #assert self.tl.is_list_of(type)
        if isinstance(self.hd, type):
            assert is_list_of(self.tl, type)
            return True
        return False
    
    def map(self, func):
        return self.tl.map(func).with_hd(func(self.hd))

    def filter(self, func):
        tl = self.tl.filter(func)
        if func(self.hd):
            return tl.with_hd(self.hd)
        return tl

class AssocList(ConsList):
    def __init__(self, key, value, tl):
        ConsList.__init__(self, (key, value), tl)

    def as_dict(self):
        return dict(self.as_list())
    
    def has_key(self, key):
        for k, v in self:
            if k == key: return True
        return False

    def __getitem__(self, key):
        for k, v in self:
            if k == key: return v
        raise KeyError(key)

    def __repr__(self):
        return repr(self.as_dict())