Python эквивалент maplist?

Question

Какой лучший Python-эквивалент функции maplist Common Lisp? Из документации списка карт :

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 не применяется к элементам этих списков. E.g.:

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

Answer 1

Вы можете написать небольшую функцию для этого

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

Answer 2

Как уже упоминали @Cybis и другие, вы не можете сохранить сложность O (N) со списками Python; вам придется создать связанный список. С риском доказать 10-е правило Гринспуна , вот такое решение:

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

Eewww ... Нарезка списка является линейной операцией. Все представленные решения имеют O (n ^ 2) временную сложность. Я считаю, что в списке Лиспа есть O (n).

Проблема в том, что тип списка Python не является связанным списком. Это динамически изменяемый размер массива (то есть, как у C ++ STL «векторного» типа).

Если для вас важно поддерживать линейную сложность времени, невозможно создать функцию «maplist» над списками Python. Было бы лучше изменить ваш код для работы с индексами в списке или преобразовать список в фактический связанный список (все еще операция с линейным временем, но с большими накладными расходами).

Answer 4

Python имеет тип связанного списка, называемый 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]]

Линейное время, делает то же самое, будет иметь те же характеристики производительности, что и операции со списками lisp (т.е. изменение внутренних элементов будет линейным по длине изменяемого списка), и та же семантика (т.е. если f изменяет список, он изменяет его для всех последующих выполнений f в рамках этого вызова maplist, однако, поскольку это создает копию lst, f не может изменить lst, в отличие от Common Lisp).

Answer 5

O (N) реализация maplist() для связанных списков

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

См. Python Linked List вопрос.

Answer 6

Вы можете использовать понимание вложенного списка:

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

Который вы можете использовать для самостоятельного определения списка карт:

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

Answer 7

это работает как ваш пример (я изменил код Рейявикви)

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

Answer 8

Изменение ответа Аарона:

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 9

Я думаю, что нет, но может работать следующая функция:

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