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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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