Почему списки различий более эффективны, чем регулярные конкатенации?

Проблема в

 ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

является гнездованием. Приложения (++) левые-вложенные, и это плохо; правой вложенности

 a ++ (b ++ (c ++ (d ++ (e ++f)))) 

не будет проблемой. Это потому, что (++) определяется как

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

поэтому, чтобы найти, какое уравнение использовать, реализация должна погрузиться в дерево выражений

  (++) / \ (++) f / \ (++) e / \ (++) d / \ (++) c / \ ab 

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

Когда конкатенации правильны, левый операнд (++) всегда находится наверху, а проверка пустоты / пузырька по голове – O (1).

Но когда конкатенации оставлены вложенными, n слоев глубокими, чтобы достигнуть первого элемента, нужно пройти n узлов дерева, для каждого элемента результата (исходящего из первого списка, n-1 для тех, которые идут от второго и т.д.).

Рассмотрим a = "hello" в

 hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

и мы хотим оценить take 5 hi . Итак, сначала нужно проверить,

 (((a ++ b) ++ c) ++ d) ++ e 

пусто. Для этого необходимо проверить,

 ((a ++ b) ++ c) ++ d 

пусто. Для этого необходимо проверить,

 (a ++ b) ++ c 

пусто. Для этого необходимо проверить,

 a ++ b 

пусто. Для этого необходимо проверить,

 a 

пусто. Уф. Это не так, поэтому мы можем снова всплыть, собирать

 a ++ b = 'h':("ello" ++ b) (a ++ b) ++ c = 'h':(("ello" ++ b) ++ c) ((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d) (((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e) ((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f) 

и для 'e' мы должны повторить, а для 'l' тоже …

Рисуя часть дерева, пузырь идет так:

  (++) / \ (++) c / \ 'h':"ello" b 

становится первым

  (++) / \ (:) c / \ 'h' (++) / \ "ello" b 

а потом

  (:) / \ 'h' (++) / \ (++) c / \ "ello" b 

вплоть до верха. Структура дерева, которая становится правильным дочерним элементом верхнего уровня (:) наконец, точно такая же, как структура исходного дерева, если только левый список пуст, когда

  (++) / \ [] b 

узлы свернуты до значения b .

Поэтому, если у вас есть вложенные вложенные конкатенации коротких списков, конкатенация становится квадратичной, поскольку для получения заголовка конкатенации используется операция O (nesting-depth). В общем, конкатенация левого гнезда

 (...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1 

O(sum [i * length a_i | i <- [1 .. d]]) для полной оценки.

С разностными списками (без новой оболочки для простоты изложения) не важно, оставлены ли композиции вложенными

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) 

или правильно вложен. После того, как вы пересекли гнездо для достижения (a ++) , то (++) поднимается вверху дерева выражений, поэтому получение каждого элемента a снова O (1).

Фактически, вся композиция повторно привязана к разностным спискам, как только вам понадобится первый элемент,

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f 

становится

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f (((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f) ((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f)) (a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f))) a ++ (b ++ (c ++ (d ++ (e ++ f)))) 

и после этого каждый список является непосредственным левым операндом верхнего уровня (++) после того, как был использован предыдущий список.

Важно то, что добавочная функция (a ++) может начать производить свой результат, не проверяя его аргумент, так что повторная ассоциация из

  ($) / \ (.) f / \ (.) (e ++) / \ (.) (d ++) / \ (.) (c ++) / \ (a ++) (b ++) 

с помощью

  ($)--------- / \ (.) ($) / \ / \ (.) (d ++) (e ++) f / \ (.) (c ++) / \ (a ++) (b ++) 

в

  ($) / \ (a ++) ($) / \ (b ++) ($) / \ (c ++) ($) / \ (d ++) ($) / \ (e ++) f 

не нужно ничего знать о составных функциях окончательного списка f , поэтому это просто переписывание O(depth) . Затем верхний уровень

  ($) / \ (a ++) stuff 

становится

  (++) / \ a stuff 

и все элементы a могут быть получены за один шаг. В этом примере, когда мы имели чистое левое гнездование, необходима только одна переписывание. Если вместо (например) (d ++) функция в этом месте была левой вложенной композицией, (((g ++) . (h ++)) . (i ++)) . (j ++) (((g ++) . (h ++)) . (i ++)) . (j ++) , переопределение верхнего уровня оставило бы это нетронутым, и это было бы повторно привязано, когда оно станет левым операндом верхнего уровня ($) после того, как все предыдущие списки будут использованы.

Общая работа, необходимая для всех повторных ассоциаций, - это O(number of lists) , поэтому общая стоимость конкатенации равна O(number of lists + sum (map length lists)) . (Это означает, что вы также можете принести плохую производительность, добавив много глубоко вложенных ([] ++) .)

 newtype DiffList a = DiffList {getDiffList :: [a] -> [a] } instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs)) 

просто обертывает это так, что более удобно обрабатывать абстрактно.

 DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++)) 

Обратите внимание, что он эффективен только для функций, которые не нуждаются в проверке их аргумента, чтобы начать выпуск вывода, если произвольные функции завернуты в DiffList s, у вас нет таких гарантий эффективности. В частности, appending ( (++ a) , завернутый или нет) может создавать левые вложенные деревья (++) когда они составлены правильно вложенными, поэтому вы можете создать поведение конкатенации O(n²) с этим, если конструктор DiffList подвергаются.

Это может помочь взглянуть на определение конкатенации:

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

Как вы можете видеть, чтобы объединить два списка, вам нужно перейти в левый список и создать «копию» его, чтобы вы могли изменить его конец (это потому, что вы не можете напрямую изменить конец старого список из-за неизменности).

Если вы выполняете свои конкатенации в правильном ассоциативном режиме, проблем нет. После того, как вы вставили, список больше не нужно будет трогать (обратите внимание, что определение ++ никогда не проверяет список справа), поэтому каждый элемент списка вставляется только «один раз» для общего времени O (N).

 --This is O(n) (a ++ (b ++ (c ++ (d ++ (e ++ f))))) 

Однако, если вы выполняете конкатенацию левым ассоциативным способом, тогда «текущий» список должен быть «снесен» и «перестроить» каждый раз, когда вы добавите еще один fragment списка в конец. Каждый элемент списка будет повторяться, когда он вставлен и всякий раз, когда будут добавлены будущие fragmentы! Это похоже на проблему, которую вы получаете на C, если вы наивно вызываете strcat несколько раз подряд.

---

Что касается списков различий, трюк заключается в том, что они видят явное «отверстие» в конце. Когда вы преобразовываете DList обратно в обычный список, вы передаете ему то, что хотите быть в яме, и оно будет готово к работе. Обычные списки, с другой стороны, всегда подключают отверстие в конце с помощью [] поэтому, если вы хотите его изменить (при конкатенации), вам нужно разорвать список, чтобы добраться до этой точки.

Определение списков разностей с функциями может сначала выглядеть пугающе, но на самом деле это довольно просто. Вы можете просматривать их с объектно-ориентированной точки зрения, считая их непрозрачными объектами. Метод «toList», который получает список, который вы должны вставить в отверстие в конце, возвращает внутренний префикс DL плюс предоставленный хвост. Это эффективно, потому что вы только затыкаете «отверстие» в конце после того, как вы закончили преобразование всего.