Правильный способ добавить элемент в конец списка?

Question

Я читал на этой странице Haskell о добавлении элемента в конец List.

Используя пример, я попробовал это для себя. Учитывая следующее List, я хотел добавить число 56 в конце.

Пример:

let numbers = [4,8,15,16,23,42] 
numbers ++ [56]

Я был сброшен этим комментарием:

Добавление элемента в конец списка - хорошее упражнение, но обычно Вы не должны делать это в реальных программах на Haskell. Это дорого, и указывает, что вы строите свой список в неправильном порядке. Есть обычно лучший подход.

Исследуя , я понимаю, что на самом деле я создаю List с 56 в качестве единственного элемента, и я объединяю его с numbers list. Это верно?

Использует ли ++ правильный способ добавить элемент в конец List?

Answer 1

++ [x] - это правильный способ добавить элемент в конец списка, но в комментарии говорится, что вы не должны добавлять элементы в конец списка.

Из-за способа определения списков добавление элемента в конце всегда требует создания копии списка. То есть

xs ++ ys

необходимо скопировать все xs, но можно повторно использовать ys без изменений.

Если xs - это всего лишь один элемент (т.е. мы добавляем в начало списка), это не проблема: копирование одного элемента практически не занимает времени совсем.

Но если xs длиннее, нам нужно провести больше времени в ++.

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

Если вам нужно сделать это, обычно есть лучший способ структурировать ваш алгоритм. Например, вы можете построить свой список в обратном порядке (добавляя элементы в начале) и вызывать только reverse в конце.

Answer 2

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

Лучший подход - выяснить, как решить вашу конкретную проблему без этого. Есть много потенциальных подходов. Выбор правильного зависит от деталей того, что вы делаете. Может быть, вы можете сойти с рук, просто используя правильно лень. Может быть, вам лучше создать список в обратном направлении, а затем в конце перевернуть его. Возможно, вам лучше использовать другую структуру данных. Все зависит от вашего конкретного случая использования.