Какой самый эффективный чисто функциональный алгоритм для генерации всех префиксов списка?

Question

prefixes ls = zipWith take [1 .. length ls] (repeat ls)

Есть ли способ добиться большего успеха, чем этот? Интуитивно, мне кажется, что невозможно получить алгоритм ниже O (n²) на чисто функциональном языке, потому что как reverse, так и append должны применяться n раз. Я понятия не имею, как это доказать.

Answer 1

Я думаю, что вы правы. Не может быть никакого разделения позвоночника в списке, потому что все хвосты разные. Таким образом, список префиксов, если он будет полностью оценен, займет полное пространство & theta;

Обратите внимание, что (более медленная версия) написанной вами функции доступна в Data.List как inits.

Однако, вы можете сделать аккуратную оптимизацию. Это уравнение справедливо:

map (foldl f z) . inits = scanl f z

И scanl работает за линейное время. Поэтому, если вы можете сформулировать то, что вы хотите сделать для каждого префикса, в виде левой складки, тогда вы можете избежать квадратичной сложности построения списка префиксов.

Answer 2

Разве это не зависит от представления?Если вы представляете списки как непрерывное хранилище плюс начальный и конечный индексы (аналогично строкам байтов), вы можете совместно использовать хранилище, и вам просто нужно пройти один раз, чтобы построить список индексов.Алгоритм не изменится, только представление.Для этого конкретного случая использования списки snoc (двоичные списки, но вложенные с конца, а не с начала списка) также позволят разделить подсписки, верно?