Есть ли в SML оператор, который позволяет мне добавлять в список, не создавая новый список? НапримерSML: Как добавить элемент в список в SML?
Я не могу это сделать:
[1,2,3]::1
, но я могу это сделать:
[1,2,3]@[1]
что странно, как я должен создать список с 1 в нем. Есть ли лучший способ сделать это?
Вы должны создать список с одним в нем в любом случае. Хвост хвоста хвоста [1,2,3,1] составляет [1]. Итак, если у вас есть [1,2,3,1] в памяти, у вас также есть [1] где-то в памяти.
Таким образом, даже если бы существовал такой оператор, как [1,2,3] @:: 1, это не повлияет, поскольку ему все еще необходимо создать список с одним в нем.
PS: Реальная проблема с xs @ [x] не является созданием списка, а тем, что его время выполнения находится в O (n) (в отличие от x :: xs, который находится в O (1)). Это также проблема, присущая природе неизменяемых односвязных списков и, следовательно, не может быть им помогла, но именно поэтому вы, как правило, должны избегать добавления к концу списка.
1. Как еще вы добавили бы список? 2. Разве они не сохраняют указатель на хвост, к которому вы добавили бы? 3. Что делает x :: xs в точности? Создать новый список или добавить к главному указателю? – Har
Являются ли списки в SML реализованы как связанные структуры или массивы? – Har
@Har SML список * неизменяемый *, односвязные списки. Они в точности эквивалентны списку данных datatype a = Минусы 'a *' списка | Nil' с 'Cons' заменяет место' :: 'и' Nil' вместо '[]'. Таким образом, у них непустой список имеет начальное значение, а другой - хвост. Ни один из них не может быть изменен. 'x :: xs' создает новый список с' x' в качестве значения главы и 'xs' в качестве хвоста. – sepp2k
[1,2,3]::1 пытается добавить список целых чисел [1,2,3] в целочисленное значение 1, к которому невозможно добавить целое число.
1::[1,2,3] однако, полностью действует, так как список [1,2,3] поддерживает операцию добавления. Правила оценки для :: требуют t1 :: t1 list, где t1 - значение от типа 1, а список t1 - это список типа 1, то, что вы делаете, - t1 list :: t1.
[1,2,3] @ [1] действителен, потому что вы добавляете список в список.
Как @ sepp2k сказал, добавление к концу списка дорого. Одним из самых медленных способов создания списка является добавление элементов один за другим до конца, поскольку любой такой подход в лучшем случае квадратичен по длине списка. По этой причине программисты SML иногда пишут функцию, которая создает списки в обратном порядке (добавление к фронту, а не назад, даже в ситуациях, когда добавление к спине кажется более естественным), а затем запустить результирующий список через 'rev' (который реализуется умным способом, так что это «O (n)»), чтобы получить нужный список. –
Нет ли указателя на хвост для добавления? который также был бы O (1) – Har
@Har Добавление к указателю на хвост (если бы даже один был, а его нет) изменил бы первоначальный список. Списки SML не изменяются, поэтому это не может быть и речи. – sepp2k