Попытка понять, как не добавлять элементы в список

Question

В качестве продолжения этого вопроса я пытаюсь понять, как не добавить элемент s к list, используя ++.

From this answer:

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

Итак, насколько я понимаю, это означает, что вы не должны делать это:

let numbers = [1,3,5,10,15]
newNumbers = numbers ++ [27]
listofnumbers = newNumbers ++ [39]

Это то, что выделено жирным шрифтом в цитируемом тексте.ответ, говорящий вам не делать?Если нет, с помощью кода, что за жирный текст предупреждает вас не делать?

Answer 1

В ответе говорится о трудной временной сложности, когда дело доходит до добавления элементов в конец списка. Когда вы объединяете список xs длины m и список ys длины n вместе, используя (++), тогда xs ++ ys будет иметь сложность времени O ( m) (в предположении вы оцениваете xs ++ ys для ряда шагов пропорционально m ).

Так что, если ваш список ys состоит из одного элемента y (то есть ys == [y]), тогда [y] ++ xs будет O (1) , потому что вы добавляете его в начало, но xs ++ [y] будет O (м) , потому что вы добавляете его в конец другого списка. Поэтому, когда вы несколько раз добавляете элементы в конец другого списка, вы получите O (m ^ 2) . Так что лучше сделайте это за один раз, чтобы у вас было O (м) .

Обратите внимание, что списки в Haskell на самом деле являются стеками, которые могут иметь бесконечное количество элементов.

Answer 2

Попробуйте эти две функции с большим списком (например, [1..10000]) и посмотрите, заметите ли вы разницу:

func1 a [] = a
func1 a (x:rest) = func (a ++ [x]) rest


func2 a b = a ++ b