Почему вы можете добавлять только списки в функциональные языки?

Я использовал только 3 функциональных языка - scala, erlang и haskell, но во всех трех из них правильный способ создания списков состоит в том, чтобы добавить новые данные на передний план, а затем перевернуть его, а не просто добавление к концу. Конечно, вы можете добавить в списки, но это приводит к созданию совершенно нового списка.

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

Ответ 1

Списки в функциональных языках неизменяемы/сохраняются.

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

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

Ответ 2

Потому что нет способа добавить к списку в O (1) без изменения оригинала (который вы не делаете на функциональных языках)

Ответ 3

Потому что быстрее

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

Ответ 4

Именно таким образом определяются списки. Список определяется как связанный список, завершаемый нулем, это не просто деталь реализации. Это, в сочетании с тем, что эти языки имеют неизменные данные, по крайней мере erlang и haskell do, означают, что вы не можете реализовать их как дважды связанные списки. Добавив элемент, они изменят список, что является незаконным.

Ответ 5

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