Почему списки F # не имеют хвостового указателя

Question

Или, если сформулировать это по-другому, какие преимущества вы получаете, имея базовый односвязный список, содержащий только указатель на голову?Преимущества указателя хвоста, который я вижу:

• O (1) конкатенация списка
• O (1) Добавление материала в правую часть списка

И то, и другое довольно удобно, в отличие от конкатенации списка O (n) (где n - длина левого списка?).Какие преимущества дает отбрасывание хвостового указателя?

Answer 1

F #, как и многие другие функциональные [-ish] языки, имеет cons-list (терминология изначально взята из LISP, но концепция такая же). В F # оператор :: (или List.Cons) используется для получения: обратите внимание, подпись ‘a –> ‘a list –> ‘a list (см. Мастеринг списков F # ).

Не путайте cons-список с непрозрачной реализацией Linked List, которая содержит дискретный первый [/ last] узел - каждая ячейка в cons-списке является началом [другого] списка! То есть «список» - это просто цепочка ячеек, которая начинается с данной cons-ячейки.

Это дает некоторые преимущества при использовании функционально-подобным образом: во-первых, все «хвостовые» ячейки являются общими и поскольку каждая конс-ячейка является неизменной («данные» могут быть изменяемыми, но это другая проблема) нет способа внести изменения в "хвостовую" ячейку и добавить все остальные списки, которые содержат указанную ячейку.

Из-за этого свойства [новые] списки могут быть эффективно построены, то есть им не требуется копия - просто с помощью cons 'вперед. Кроме того, очень эффективно деконструировать список до head :: tail - опять же, без копирования - что часто очень полезно в рекурсивных функциях.

Это неизменяемое свойство обычно не существует в реализации [стандартного изменяемого] двойного связанного списка, в этом добавлении добавляются побочные эффекты: внутренний «последний» узел (тип теперь непрозрачный) и одна из «хвостовых» ячеек изменены (Существует типов неизменяемых последовательностей, которые позволяют добавлять / обновлять «эффективно постоянное время», например immutable.Vector в Scala - однако, это более тяжелые объекты по сравнению с минусами -список, представляющий собой не более чем серию ячеек, объединенных вместе.)

Как уже упоминалось, есть и недостатки, что cons-list не подходит для всех задач - в частности, создание нового списка, за исключением cons , связанного с заголовком, является операцией O (n), фсво, а к лучшему (или худшему) список неизменен.

Я бы порекомендовал создать собственную версию concat, чтобы увидеть, как эта операция действительно выполняется. (Статья Почему я люблю F #: Списки - Основы охватывает это.)

Удачного кодирования.

---

Также см. Связанный пост: Почему вы можете добавлять к спискам только функциональные языки?

Answer 2

F # списки являются неизменяемыми, не существует такой вещи, как "append / concat", скорее, это просто создание новых списков (которые могут повторно использовать некоторые суффиксы старых списков).Неизменность имеет много преимуществ, выходящих за рамки этого вопроса.(Все чистые языки и большинство функциональных языков имеют такую ​​структуру данных, это не F # -изм.)

См. Также

http://diditwith.net/2008/03/03/WhyILoveFListsTheBasics.aspx

, которая имеет хорошую картинудиаграммы для объяснения (например, почему постоянный список дешевле, чем окончательный список).

Answer 3

В дополнение к тому, что говорили другие: если вам нужны эффективные, но все же неизменные структуры данных (что должно быть идиоматическим способом F #), вы должны рассмотреть чтение Крис Окасаки, Чисто функциональные структуры данных .Существует также тезис (на котором основана книга).

Answer 4

В дополнение к тому, что уже было сказано, в разделе Введение в функциональное программирование в MSDN есть статья о Работа с функциональными списками , которая объясняет, как работают списки, а также реализует их в C # , так что это может быть хорошим способом понять, как они работают (и почему добавление ссылки на последний элемент не позволит эффективно реализовать append).

Если вам нужно добавить что-то в конец списка, а также в начало, то вам нужна другая структура данных. Например, Норман Рэмси опубликовал исходный код для DList, который имеет эти свойства здесь (реализация не идиоматическая F #, но ее легко исправить).

Answer 5

Если вам нужен список с более высокой производительностью для операций добавления, взгляните на QueueList в F # PowerPack и JoinList в расширении FSharpx. библиотеки.

QueueList инкапсулирует два списка. Когда вы добавляете «против», он добавляет элемент в первый список, как список «против». Однако, если вы хотите добавить один элемент, его можно перенести в начало второго списка. Когда в первом списке заканчивается элемент, во втором списке запускается List.rev, и они меняются местами, приводя ваш список в порядок и освобождая второй список для добавления новых элементов.

JoinList использует дискриминационное объединение для более эффективного добавления целых списков и немного сложнее.

Очевидно, что оба они менее производительны для стандартных операций, но предлагают лучшую производительность для других сценариев.

Подробнее об этих структурах можно прочитать в статье Рефакторинг сопоставления с образцом .

Answer 6

Или, если сформулировать это по-другому, какие преимущества вы получаете, имея базовый односвязный список, содержащий только указатель на голову? Преимущества указателя хвоста, который я вижу:

• O (1) конкатенация списков
• O (1) Добавление материала в правую часть списка

Обе эти вещи довольно удобны, в отличие от конкатенации O (n) списков (где n - длина левого списка?).

Если под «указателем хвоста» вы имеете в виду указатель из каждого списка на последний элемент в списке, то он сам по себе не может быть использован для предоставления какого-либо из цитируемых вами преимуществ. Хотя вы могли бы быстро добраться до последнего элемента в списке, вы ничего не можете с ним сделать, потому что он неизменен.

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

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

Какими преимуществами обладает отбрасывание хвостового указателя?

На 30% меньше места и лучшая производительность практически для всех операций со списками.

Answer 7

Как уже отмечали другие, список F # может быть представлен структурой данных:

List<T> { T Value; List<T> Tail; }

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

Тем не менее, ваш первоначальный вопрос, кажется, почему список не определен больше как:

List<T> { Node<T> Head; Node<T> Tail; }
Node<T> { T Value; Node<T> Next; }

Такая структура позволила бы добавлять и добавлять в список без видимых эффектов ссылку на исходный список, поскольку она все еще видит только «окно» расширенного списка. Хотя это (иногда) допускает конкатенацию O (1), существует несколько проблем, с которыми столкнется эта функция:

• Конкатенация работает только один раз. Это может привести к неожиданному поведению производительности, когда одна конкатенация - O (1), а следующая - O (n). Скажем, например:

   listA = makeList1 ()
   listB = makeList2 ()
   listC = makeList3 ()
   listD = listA + listB //modified Node at tail of A for O(1)
   listE = listA + listC //must now make copy of A to concat with C
  

  Можно утверждать, что экономия времени для случаев, где это возможно, того стоит, но неожиданность того, что вы не знаете, когда это будет O (1) и когда O (n), являются сильными аргументами против этой функции.

• Все списки теперь занимают вдвое больше места, даже если вы никогда не планируете их объединять.
• Теперь у вас есть отдельный список и тип узла. Я полагаю, что в текущей реализации F # использует только один тип, такой как начало моего ответа. Может быть способ сделать то, что вы предлагаете, только одним типом, но для меня это не очевидно.
• Конкатенация требует изменения исходного экземпляра "хвостового" узла. Хотя это не должно влиять на программы, оно является точкой мутации, которой большинство функциональных языков избегают.