Вносит ли добавление списка в другой список в F# копирование базовых объектов или только указателей?

Question

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

Answer 1

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

Если вы имеете в виду это утверждение, то ответ кажется довольно простым. Автор первой статьи говорит об элементах списка, когда говорит nodes, Элемент Node не совпадает с самим элементом списка. Посмотрите на фотографии в первой статье. Есть стрелки, идущие от каждого элемента к следующему узлу. Эти стрелки являются указателями. Но целочисленный тип (который заносится в список) не имеет таких указателей. Есть, вероятно, некоторые list node тип, который упаковывает эти целые числа и хранит указатели. Когда автор говорит, что nodes must be copies он говорит о том, что эти обертки копируются. Базовые объекты (если они не были типами значений, как в этом случае) не будут клонированы, новые оболочки будут указывать на тот же объект, что и раньше.

Answer 2

Исходя из ответа Snowbear, более точное изображение объединения двух списков (чем представленное в первой упомянутой статье в вопросе) будет таким, как показано ниже.

let FIRST = [1;2;3]
let SECOND = [4;5;6]
let COMBINED = FIRST @ SECOND

Answer 3

Списки F# содержат ссылки (не путать с F# ref) к их элементам; Операции со списками копируют эти ссылки (указатели), но не сами элементы.

Есть два способа добавить элементы в существующий список, поэтому кажется, что между статьями есть расхождение (хотя обе они выглядят правильными):

• Минусы оператора (::): Оператор cons добавляет один элемент к списку F#, создавая новый список. Это очень быстро (O(1)), поскольку для создания нового списка требуется только очень простой конструктор.
• Добавить оператор (@): Оператор добавления добавляет два списка F# вместе, создавая новый список. Это не так быстро (O(n)) потому что для правильного упорядочения элементов объединенного списка необходимо пройти по всему списку слева от оператора (поэтому копирование может начинаться с первого элемента этого списка). Вы по-прежнему будете использовать его в работе, если известно, что список слева очень мал, но в целом вы получите гораздо лучшую производительность от использования. ::,