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

Question

Поскольку :: : 'a -> 'a list -> 'a list используется для добавления элемента в начало списка, может кто-нибудь сказать мне, есть ли функция для добавления элемента в конец элемента список? Если нет, то я думаю, List.rev (element::(List.rev list)) - самый простой способ сделать это?

Спасибо!

Answer 1

Причина, по которой для этого нет стандартной функции, заключается в том, что добавление в конец списка - это анти-паттерн (он же "список snoc" или алгоритм Шлемеля Пейнтера ).Для добавления элемента в конец списка требуется полная копия списка.Добавление элемента в начале списка требует выделения одной ячейки - хвост нового списка может просто указывать на старый список.

При этом самый простой способ сделать это -

let append_item lst a = lst @ [a]

Answer 2

list@[element] должно работать.@ присоединяется к спискам.

Answer 3

Учитывая, что эта операция является линейной, вы не должны использовать ее в «горячей» части вашего кода, где важна производительность. В холодной части используйте list @ [element], как предложено Adi. В горячей части, перепишите свой алгоритм, так что вам не нужно это делать.

Типичный способ сделать это - накапливать результаты в порядке обратный во время обработки, а затем переворачивать весь накопленный список перед возвратом результата. Если у вас есть N этапов обработки (каждый из которых добавляет элемент в список), вы поэтому амортизируете линейную стоимость реверса по N элементам, поэтому вы сохраняете линейный алгоритм вместо квадратичного.

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