Python中maplist的等价方法是什么？

Question

Python中有没有类似于Common Lisp的maplist函数的最佳替代品？在maplist的文档中，这样解释：

maplist的工作方式类似于mapcar，但它是对列表的每个子列表依次应用函数。首先，函数会应用到整个列表上，然后再应用到每个列表的cdr（也就是去掉第一个元素后的部分），接着再对cdr的cdr进行处理，依此类推。

举个例子（伪代码，未测试）：

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

注意：上面例子中传给p的参数会是列表[1, 2, 3]、[2, 3]、[3]；也就是说，p并不是应用于这些列表的元素。例如：

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

Answer 1

哎呀... 切片一个列表的操作是线性的，也就是说它的速度和列表的长度成正比。到目前为止，大家提供的解决方案时间复杂度都是O(n^2)，也就是速度会随着列表长度的平方增加。我觉得Lisp里的maplist函数是O(n)，也就是速度比较快。

问题在于，Python的列表类型并不是链表，而是动态可调整大小的数组（就像C++ STL里的“vector”类型）。

如果你想保持线性时间复杂度，那在Python的列表上创建一个“maplist”函数是不可能的。更好的办法是修改你的代码，让它使用列表的索引，或者把列表转换成真正的链表（这也是线性时间操作，但会有很多额外的开销）。

Answer 2

正如 @Cybis 和其他人提到的，使用 Python 列表时，你无法保持 O(N) 的复杂度；你需要创建一个链表。虽然这样做可能会证明 格林斯潘的第十条规则，但这里有一个这样的解决方案：

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

测试结果如下：

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

编辑：这里有一个基于生成器的解决方案，基本上可以在不使用链表的情况下解决同样的问题：

import itertools

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

测试结果如下：

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

Answer 3

你可以为这个写一个小函数。

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

[编辑]

如果你想在子列表上使用这个函数，可以把函数改成这样：

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