Понимание концепции списков различий

Question

Когда я читал главу 13 из Real World Haskell, я натолкнулся на концепцию Difference Lists.
Автор говорит, что на императивном языке, если мы хотим добавить элемент в список, стоимость будет O(1), поскольку мы сохраним указатель на последний элемент.Однако в Haskell у нас есть immutable объектов, поэтому нам нужно было бы каждый раз просматривать список и добавлять элемент в конце, таким образом 0(n).

Вместо [1,2,3]++[4]++[5]
мы могли бы использоватьчастичное применение: (++4).(++5) [1,2,3].

Я не понимаю, как это более эффективно, поскольку:
- когда я делаю (++[5]) [1,2,3], это все равно будет O(n), а затем еще один 0(n) для (++4)

Цитата

There are two very interesting things about this approach. The first is that the cost of a partial application is constant, so the cost of many partial applications is linear. The second is that when we finally provide a [] value to
unlock the final list from its chain of partial applications, application 
proceeds from right to left. This keeps the left operand of (++) small, and so 
the overall cost of all of these appends is linear, not quadratic

Я понимаю, что такой подход был бы нетерпеливым, поэтому вместо того, чтобы оставить броски yet to be applied methods, мы оставим левый операнд small как говорит автор, но .... мы по-прежнему выполняем обход каждого добавления.

Учитывая список: [1...100] и желая добавить 1,2, я бы все равно прошел его 2 разтак как я бы:

1. f(f([1..100]))= f([1..100,1]) - прошел 1 раз и добавил 1

2. [1..100,1,2] - прошел второйвремя для добавления 2

Может кто-нибудь осветить меня, как это более эффективно с точки зрения сложности времени?(потому что space -сложность обусловлена ​​не более thunks, например foldl')

---

PS

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

Если я использую f=(:) на a= [1,2,3]:
(f 4 . f 5) $ a
Я мог бы сказать, что у меня была 0(1) эффективность на каждом добавлении, так как я всегда добавлялся кслева, но я бы не получил [1,2,3,4,5], я бы получил [5,4,1,2,3], так как в этом случае difference list более эффективен для однократной операции добавления одного элемента?

Answer 1

Вам нужно быть более осторожным со временем, то есть , когда происходит то или иное.

Вместо того, чтобы начинать со списка [1,2,3], с другими списками, которые мы начинаем с

f1 = ([1,2,3] ++)

Затем, чтобы «добавить» 4, 5, в конец растущего списка разница , мы имеем

f2 = f1 . ([4] ++)
f3 = f2 . ([5] ++)

Каждое такое добавление вконец растущего списка различий равен O (1) .

Когда мы наконец закончим его создание, мы преобразуем его в «нормальный» список по приложению

xs = f3 []    -- or f3 [6..10] or whatever

Затем, осторожно, мы получаем

xs = ((([1,2,3] ++) . ([4] ++)) . ([5] ++)) []
   =  (([1,2,3] ++) . ([4] ++)) ( ([5] ++)  [] )
   =   ([1,2,3] ++) ( ([4] ++)  ( ([5] ++)  [] ))
   =     1:2:3:     (   4  :    (   5  :    [] ))

по определению (++).

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

---

Четный a1 = (++ [4]) [1..] сам по себе - это операция O (1) , а также a2 = (++ [5]) a1 и a3 = (++ [6]) a2, потому что Haskell ленив, а создание thunk - O (1) .

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

Преобразование в обычный список с применением вложенного слеваСтруктура . в [] перестраивает внутреннюю структуру в структуру $ с правой вложенностью, как объяснено в каноническом ответе, поэтому повторный доступ к такой структуре сверху линейный.

Таким образом,разница между ((++ [5]) . (++ [4])) [1,2,3] (плохо) и ((([1,2,3] ++) . ([4] ++)) . ([5] ++)) [] (хорошо).Построение цепочки функций ((++ [4]) . (++ [5])) само по себе является линейным, да, но оно создает структуру, квадратичную для полного доступа.

Но ((([1,2,3] ++) . ([5] ++)) . ([4] ++)) [] становится ([1,2,3] ++) (([5] ++) (([4] ++) [])).