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

Question

Пока я читал главу 13 из Real World Haskell я натолкнулся на концепцию Difference Lists,
Автор говорит, что на императивном языке, если мы хотим добавить элемент в список, стоимость будет O(1) так как мы будем держать указатель на последний элемент. Однако в Хаскеле мы имеем 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] ++) [])),