Python equivalent of maplist?

Question

What's the best Python equivalent of Common Lisp's maplist function? From the maplist documentation:

maplist is like mapcar except that function is applied to successive sublists of the lists. function is first applied to the lists themselves, and then to the cdr of each list, and then to the cdr of the cdr of each list, and so on.

Example (pseudoy-code, not tested):

>>> def p(x): return x
>>> maplist(p, [1,2,3])
[[1, 2, 3], [2, 3], [3]]

Note: the arguments passed to p in the example above would be the lists [1, 2, 3], [2, 3], [3]; i.e., p is not applied to the elements of those lists. E.g.:

>>> maplist(lambda l: list(reversed(l)), [1,2,3])
[[3, 2, 1], [3, 2], [3]]

Answer 1

You can write a little function for that

def maplist(func, values):
    return [map(func, values[i:]) for i in xrange(len(values))]

>>> maplist(lambda a: a* 2, [1,2,3])
[[2, 4, 6], [4, 6], [6]]

[Edit]

if you want to apply the function on the sublists you can change the function to this:

def maplist(func, values):
    return [func(values[i:]) for i in xrange(len(values))]

>>> maplist(lambda l: list(reversed(l)), [1,2,3])
[[3, 2, 1], [3, 2], [3]]

Answer 2

As @Cybis and others mentioned, you can't keep the O(N) complexity with Python lists; you'll have to create a linked list. At the risk of proving Greenspun's 10th rule, here is such a solution:

class cons(tuple):
    __slots__=()

    def __new__(cls, car, cdr):
        return tuple.__new__(cls, (car,cdr))

    @classmethod
    def from_seq(class_, l):
        result = None
        for el in reversed(l):
            result = cons(el, result)
        return result

    @property
    def car(self): return self._getitem(0)

    @property
    def cdr(self): return self._getitem(1)

    def _getitem(self, i):
        return tuple.__getitem__(self, i)

    def __repr__(self):
        return '(%s %r)' % (self.car, self.cdr)

    def __iter__(self):
        v = self
        while v is not None:
            yield v.car
            v = v.cdr

    def __len__(self):
        return sum(1 for x in self)

    def __getitem__(self, i):
        v = self
        while i > 0:
            v = v.cdr
            i -= 1
        return v.car

def maplist(func, values):
    result = [ ]
    while values is not None:
        result.append(func(values))
        values = values.cdr
    return result

Testing yields:

>>> l = cons.from_seq([1,2,3,4])
>>> print l
(1 (2 (3 (4 None))))
>>> print list(l)
[1, 2, 3, 4]
>>> print maplistr(lambda l: list(reversed(l)), cons.from_seq([1,2,3]))
[[3, 2, 1], [3, 2], [3]]

EDIT: Here is a generator-based solution that basically solves the same problem without the use of linked lists:

import itertools

def mapiter(func, iter_):
    while True:
        iter_, iter2 = itertools.tee(iter_)
        iter_.next()
        yield func(iter2)

Testing yields:

>>> print list(mapiter(lambda l: list(reversed(list(l))), [1,2,3]))
[[3, 2, 1], [3, 2], [3]]