Онлайн-алгоритм Haskell с линейным временем

Haskell и хвостовая рекурсия не ладят так же хорошо, как другие функциональные языки и хвостовая рекурсия. Давайте вручную уменьшим очень простой код, чтобы увидеть, что происходит с хвостовой рекурсией. Вот реализация хвостовой рекурсии map (1+).

go [] r = r
go (x:xs) r = go xs (r ++ [1+x])

Также мы должны помнить об определении (++):

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Теперь давайте уменьшим go [1,2,3,4,5] []. Имейте в виду, что [x,y,z] обозначает x:(y:(z:[])) или сокращенно x:y:z:[].

go [1,2,3,4,5] []
go [2,3,4,5] ([] ++ [2])   -- 2 here is actually the thunk 1+1, but
                           -- for compactness I am reducing earlier
go [3,4,5] (([] ++ [2]) ++ [3])
go [4,5] ((([] ++ [2]) ++ [3]) ++ [4])
go [5] (((([] ++ [2]) ++ [3]) ++ [4]) ++ [5])
go [] ((((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6])
(((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6]
((([2] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(((2:([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
((2:(([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(2:((([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
2:(((([] ++ [3]) ++ [4]) ++ [5]) ++ [6])    -- first observable output
2:((([3] ++ [4]) ++ [5]) ++ [6])
2:((3:([] ++ [4]) ++ [5]) ++ [6])
2:(3:(([] ++ [4]) ++ [5]) ++ [6])
2:3:((([] ++ [4]) ++ [5]) ++ [6])           -- second observable output
2:3:(([4] ++ [5]) ++ [6])
2:3:(4:([] ++ [5]) ++ [6])
2:3:4:(([] ++ [5]) ++ [6])                  -- third observable output
2:3:4:([5] ++ [6])
2:3:4:5:([] ++ [6])                         -- fourth observable output
2:3:4:5:6:[]                                -- final output

Видите, как каждый элемент в выходных данных должен выходить наружу из глубоко вложенных скобок? Это приводит к тому, что для получения всего вывода требуется квадратичное время по размеру ввода. Вы также увидите поведение, при котором первые несколько элементов выдаются медленно, и оно становится все быстрее и быстрее по мере того, как вы достигаете конца списка. Это сокращение объясняет это.

Основной проблемой производительности здесь является добавление нового элемента в конец списка, что занимает время, пропорциональное размеру списка, к которому вы добавляете. Лучший способ - использовать cons на переднем плане, что является постоянной операцией. Это приведет к тому, что вывод будет обратным, поэтому вам нужно изменить результат.

go [] r = reverse r
go (x:xs) r = go xs ((1+x):r)

reverse xs = rev xs []      -- roughly from the report prelude
rev [] r = r
rev (x:xs) r = rev xs (x:r)

И давайте уменьшим:

go [1,2,3,4,5] []
go [2,3,4,5] [2]
go [3,4,5] [3,2]
go [4,5] [4,3,2]
go [5] [5,4,3,2]
go [] [6,5,4,3,2]
reverse [6,5,4,3,2]
rev [6,5,4,3,2] []
rev [5,4,3,2] [6]
rev [4,3,2] [5,6]
rev [3,2] [4,5,6]
rev [2] [3,4,5,6]
rev [] [2,3,4,5,6]
[2,3,4,5,6]          -- first and all observable output!

Так что это явно меньше работы, чем первая версия. Этот стиль используется в строгих языках, таких как Scheme и ML, потому что он имеет хорошую производительность памяти. Однако у него есть некоторые недостатки:

• Все входные данные должны быть потреблены, прежде чем можно будет произвести какой-либо выход. Действительно, все вычисления выполняются до того, как будут получены какие-либо результаты.
• Из-за этого он никогда не дает никакого вывода при задании бесконечного списка.
• Это включает в себя reverse, что занимает дополнительное O(n) время и не имеет ничего общего с тем, что мы делаем (какое отношение реверсирование имеет к добавлению единицы к каждому элементу и сохранению порядка?).

На таком ленивом языке, как Haskell, мы можем добиться большего. Удивительно и прекрасно то, что мы делаем это, написав это еще более наивно.

go [] = []
go (x:xs) = (1+x):go xs

и уменьшить:

go [1,2,3,4,5]
2:(go [2,3,4,5])     -- first observable output
2:3:(go [3,4,5])     -- second observable output
2:3:4:(go [4,5])     -- third observable output
2:3:4:5:(go [6])     -- fourth observable output
2:3:4:5:6:(go [])    -- fifth observable output
2:3:4:5:6:[]         -- final output

Он требует еще меньше усилий и начинает выдавать результат еще до того, как просмотрит оставшуюся часть списка, поэтому он имеет хорошую производительность в потоковых вычислениях и работает с бесконечными входными данными. И реализация настолько проста и очевидна, насколько вы могли надеяться.

Я надеюсь, что это дало вам некоторое представление о том, как хвостовая рекурсия работает в Haskell. Для вашего примера я предлагаю удалить хвостовую рекурсию и переписать в наивном стиле, похожем на наш окончательный go, используя интуицию, которую я надеюсь, что предложил из этого поста, чтобы получить «как можно больший префикс ввода, как можно скорее» (обратите внимание, что возврат x:xs немедленно дает x, даже если для вычисления xs нужно проделать дополнительную работу — это лень в (не-)действии).