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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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

A more accurat description of appended list

Ответ 3

F # перечисляет ссылки (не путать с F # ref) с их элементами; список операций копирует эти ссылки (указатели), но не сами элементы.

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

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