Вам нужно быть более осторожным со временем, то есть , когда происходит то или иное.
Вместо того, чтобы начинать со списка [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] ++) []))
.