Python, эквивалентный из maplist?

Как упоминалось @Cybis и другими, вы можете ' t сохранить сложность 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]]

Фууууу ... Нарезка списка - это операция линейного времени. Все опубликованные решения имеют временную сложность O (n ^ 2). Я считаю, что список отображения Lisp имеет O (n).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Вопрос Связанный список Python .