Как к concat перечисляет в erlang, не создавая вложенные списки?
Я пытаюсь быть хорошим Эрлангером и избежать "++". Я должен добавить кортеж в конец списка, не создавая вложенный список (и надо надеяться не имея необходимость создавать его назад и инвертировать его). Учитывая кортеж T и списки L0 и L1:
Когда я использую [T|L0], я получаю [кортеж, list0].
Но когда я использую [L0|T], я получаю вложенный список [[list0]|tuple]. Точно так же [L0|L1] возвраты [[list0]|list1].
При удалении внешних скобок списка L0 | [T] производит синтаксическую ошибку.
Почему "|" не симметричен? Существует ли способ сделать то, что я хочу использовать "|"?
1 ответ
| не является "симметричным", потому что непустой список имеет голову и хвост, где голова - это один элемент, а хвост - другой список. В выражении [foo | bar] foo обозначает голову списка, а bar - хвост. Если хвост не является правильным списком, то и результат не будет правильным списком. Если голова является списком, то результатом будет просто список с этим списком в качестве первого элемента.
Не существует способа добавить в конец связного списка за время меньше O(n). Вот почему использование ++ для этого обычно избегают. Если бы существовал специальный синтаксис для добавления в конец списка, это все равно заняло бы время O(n), и использование этого синтаксиса не сделало бы вас более "хорошим эрландером", чем использование ++.
Если вы хотите избежать затрат O(n) на вставку, вам нужно будет выполнить препендинг, а затем реверс. Если вы готовы заплатить за это, то с тем же успехом можно использовать ++.
Немного подробнее о том, как работают списки:
[ x | y ] - это то, что называется ячейкой cons. В терминах языка Си это, по сути, структура с двумя членами. Правильный список - это либо пустой список ([]), либо ячейка cons, второй член которой - правильный список (в этом случае первый член называется головой, а второй - хвостом).
Поэтому, когда вы пишете [1, 2, 3], это создает следующие cons-ячейки: [1 | [2 | [3 | []]]]. Т.е. список представлен в виде cons-ячейки, первым членом которой (головой) является 1, а вторым членом (хвостом) - другая cons-ячейка. Эта другая ячейка имеет 2 в качестве головы и еще одну ячейку в качестве хвоста. Эта ячейка имеет 3 в качестве головы и пустой список в качестве хвоста.
Обход такого списка выполняется рекурсивно, сначала действуя на голову списка, а затем вызывая функцию обхода на хвост списка.
Теперь, если вы хотите добавить элемент в этот список, это очень просто: вы просто создаете еще одну ячейку cons, голова которой - новый элемент, а хвост - старый список.
Однако добавление элемента требует гораздо больших затрат, потому что одной ячейки cons недостаточно. Вы должны создать список, который будет таким же, как и старый, за исключением того, что хвост последней cons-ячейки должен быть новой cons-ячейкой, голова которой - новый элемент, а хвост - пустой список. Таким образом, вы не можете добавлять к списку, не пройдя через весь список, что является O(n).