Каков наиболее эффективный чисто функциональный алгоритм для генерации всех префиксов списка?
prefixes ls = zipWith take [1 .. length ls] (repeat ls)
Есть ли способ сделать это лучше? Интуитивно, мне кажется, что невозможно получить алгоритм ниже O (n²) в чисто функциональном языке, потому что либо обратное, либо добавление должно применяться n раз. Я даже не знаю, как это доказать.
Ответы
Ответ 1
Я думаю, что ты прав. Не может быть обмена позвоночника в списке, потому что все хвосты разные. Поэтому список префиксов, если они были полностью оценены, займет полное пространство & Theta; (n 2), которое должно взять время & Omega; (n 2) для генерации.
Обратите внимание, что (более ленивая версия) функция, которую вы написали, доступна в Data.List как inits.
Существует оптимизированная оптимизация, которую вы можете сделать. Это уравнение имеет место:
map (foldl f z) . inits = scanl f z
И scanl работает в линейном времени. Поэтому, если вы можете сформулировать то, что хотите сделать для каждого префикса, как левую сгиб, тогда вы можете избежать квадратичной сложности построения списка префиксов.
Ответ 2
Разве это не зависит от представления? Если вы представляете списки как непрерывное хранилище плюс индекс начала и конца (аналогично байтам), вы можете совместно использовать хранилище и просто нужно пройти один раз, чтобы создать список индексов. Алгоритм не изменился бы, просто представление. Для этого конкретного случая использования, используя списки snoc (двоичные списки, но вложенные с конца, а не в начало списка), также разрешает совместное использование подписок, правильно?
