Как составить списки в erlang без создания вложенных списков?

Question

Я стараюсь быть хорошим erlanger и избегать «++». Мне нужно добавить кортеж в конец списка без создания вложенного списка (и, надеюсь, без необходимости его создания назад и наоборот). Учитывая кортеж Т и списки L0 и L1:

Когда я использую [T | L0] я [кортеж, песни0].

Но когда я использую [L0 | T], я получаю вложенный список [[песни0] | кортеж]. Аналогичным образом, [L0 | L1][[список0] | список1].

Извлечение скобок внешнего списка L0 | [T] создает синтаксическую ошибку.

Почему «|» несимметричный? Есть ли способ сделать то, что я хочу, используя «|»?

Answer 1

| не является «симметричным», потому что в непустом списке есть голова и хвост, где голова представляет собой отдельный элемент, а хвост - другой список. В выражении [foo | bar]foo обозначает головку списка, а bar - это хвост. Если хвост не является правильным списком, результат также не будет правильным. Если голова - это список, результат будет просто списком с этим списком в качестве его первого элемента.

Невозможно добавить в конец связанного списка менее чем за время O (n). Вот почему использование ++ для этого обычно избегается. Если бы был специальный синтаксис для добавления в конце списка, все равно нужно было бы взять время O (n), и использование этого синтаксиса не сделало бы вас более «хорошим erlanger», чем использование ++.

Если вы хотите избежать стоимости O (n) за вставку, вам необходимо добавить и затем перевернуть. Если вы готовы оплатить расходы, вы можете использовать ++.

Чуть более подробно о том, как работают списки:

[ x | y ] что-то называется минусы клетки. В терминах C это в основном структура с двумя членами. Правильный список - это либо пустой список ([]), либо ячейка cons, второй член которой является правильным списком (в этом случае первый член называется его головой, а второй - хвостом).

Поэтому, когда вы пишете [1, 2, 3], это создает следующие ячейки cons: [1 | [2 | [3 | []]]]. То есть список представлен как ячейка cons, чей первый член (его голова) равен 1, а второй член (хвост) является другой cons-ячейкой. Эта другая ячейка cons имеет 2 в качестве головы и еще одну cons-клетку в качестве ее хвоста. Эта ячейка имеет 3 в качестве головы, а пустой список - как хвост.

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

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

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