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

I think there isn't, but the following function can work:

def maplist(func, l):
    for i in range(len(l)):
        func(l[i:])

Answer 3

this works like your example (I've modified reyjavikvi's code)

def maplist(func, l):
    result=[]
    for i in range(len(l)):
        result.append(func(l[i:]))
    return result

Answer 4

You can use nested list comprehensions:

>>> def p(x): return x
>>> l = range(4)[1:]
>>> [p([i:]) for i in range(len(l))]
[[1, 2, 3], [2, 3], [3]]

Which you can use to define maplist yourself:

>>> def maplist(p, l): return [p([i:]) for i in range(len(l))]
>>> maplist(p, l)
[[1, 2, 3], [2, 3], [3]]

Answer 5

Modifying Aaron's answer:

In [8]: def maplist(p, l): return [p([x for x in l[i:]]) for i in range(len(l))]
   ...: 

In [9]: maplist(lambda x: x + x, [1,2,3])
Out[9]: [[1, 2, 3, 1, 2, 3], [2, 3, 2, 3], [3, 3]]

Answer 6

Eewww... Slicing a list is a linear-time operation. All of the solutions posted thus far have O(n^2) time complexity. Lisp's maplist, I believe, has O(n).

The problem is, Python's list type isn't a linked list. It's a dynamically resizable array (i.e., like C++ STL's "vector" type).

If maintaining linear time complexity is important to you, it isn't possible to create a "maplist" function over Python lists. It would be better to modify your code to work with indices into the list, or convert the list into an actual linked list (still a linear-time operation, but would have a lot of overhead).

Answer 7

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]]

Answer 8

O(N) implementation of maplist() for linked lists

maplist = lambda f, lst: cons(f(lst), maplist(f, cdr(lst))) if lst else lst

See Python Linked List question.