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

Answer 3

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 4

Python has a linked list type, called deque:

from collections import deque

def maplist(f, lst):
    linked = deque(lst)
    results = []
    while linked:
        results.append(f(linked))
        linked.popleft() # assumes left is head, as in lisp

    return results

In [134]: maplist(lambda l: list(reversed(l))*2, [1,2,3])
Out[134]: [[3, 2, 1, 3, 2, 1], [3, 2, 3, 2], [3, 3]]

Linear time, does the same thing, will have the same performance characteristics as operations on lisp lists (i.e. modifying interior elements will be linear in the length of the list being modified), and the same semantics (i.e. if f modifies the list, it modifies it for all subsequent executions of f within that maplist call; however, because this creates a copy of lst, f cannot modify lst, unlike in Common Lisp).

Answer 5

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 6

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 7

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

Answer 9

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

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