Двусвязный список имеет минимальные накладные расходы (просто еще один указатель на ячейку) и позволяет добавлять к обоим концам, переходить назад и вперед и, как правило, получать массу удовольствия.
data-structures
functional-programming
Эллиот Гороховский
источник
источник
next
указатель предыдущего элемента указывал на следующий элемент, аprev
указатель следующего элемента указывал на предыдущий элемент. Однако один из этих двух элементов создается раньше другого, что означает, что один из этих элементов должен иметь указатель, указывающий на объект, который еще не существует! Помните, вы не можете сначала создать один элемент, затем другой, а затем установить указатели - они неизменны. (Примечание: я знаю, что есть способ, использующий лень, который называется «Связывание узла».)Ответы:
Что ж, если вы посмотрите немного глубже, на самом деле оба включают массивы и на базовом языке:
Однако в инструкциях по функциональному программированию долгое время подчеркивались односвязные списки над массивами или двусвязные списки. Вполне вероятно, переоценена, на самом деле. Однако для этого есть несколько причин.
Во-первых, односвязные списки являются одним из самых простых и в то же время наиболее полезных рекурсивных типов данных. Пользовательский эквивалент типа списка Haskell может быть определен следующим образом:
Тот факт, что списки являются рекурсивными типами данных, означает, что функции, работающие со списками, обычно используют структурную рекурсию . В терминах Haskell: вы сопоставляете шаблон с конструкторами списка, и вы повторяете на части списка. В этих двух основных определениях функций я использую переменную
as
для ссылки на конец списка. Обратите внимание, что рекурсивные вызовы «спускаются» вниз по списку:Этот метод гарантирует, что ваша функция завершится для всех конечных списков, а также является хорошим методом решения проблем - он имеет тенденцию естественным образом разбивать проблемы на более простые и более подходящие части.
Таким образом, односвязные списки, вероятно, являются лучшим типом данных для ознакомления учащихся с этими методами, которые очень важны в функциональном программировании.
Вторая причина - это не столько причина «почему односвязные списки», сколько причина «почему не двойные списки или массивы»: эти последние типы данных часто требуют мутации (изменяемые переменные), что очень часто используется в функциональном программировании. уклоняется от. Итак, как это происходит:
vector
, однако, нашли методы, которые значительно улучшают эту проблему).Третья и последняя причина относится в первую очередь к ленивым языкам, таким как Haskell: ленивые односвязные списки на практике часто больше похожи на итераторы, чем на собственно списки в памяти. Если ваш код потребляет элементы списка последовательно и выбрасывает их по ходу работы, объектный код материализует только ячейки списка и его содержимое по мере продвижения по списку.
Это означает, что весь список не должен существовать в памяти сразу, только текущая ячейка. Ячейки до текущей могут быть собраны мусором (что было бы невозможно с двойным списком); ячейки позже текущей не нужно вычислять, пока вы не доберетесь туда.
Это идет даже дальше, чем это. Существует методика, используемая в нескольких популярных библиотеках Haskell, которая называется fusion , где компилятор анализирует ваш код обработки списков и определяет промежуточные списки, которые генерируются и используются последовательно, а затем «выбрасываются». Обладая этими знаниями, компилятор может полностью исключить выделение памяти для ячеек этих списков. Это означает, что односвязный список в исходной программе на Haskell после компиляции может фактически превратиться в цикл вместо структуры данных.
Fusion также является техникой, которую упомянутая
vector
библиотека использует для генерации эффективного кода для неизменяемых массивов. То же самое относится и к чрезвычайно популярным библиотекамbytestring
(массивы байтов) иtext
(строки Unicode), которые были построены в качестве замены не очень большого нативногоString
типа Хаскелла (который аналогичен[Char]
односвязному списку символов). Таким образом, в современном Haskell наблюдается тенденция, когда типы неизменяемых массивов с поддержкой fusion становятся очень распространенными.Слияние списков облегчается тем фактом, что в единственном связанном списке вы можете двигаться вперед, но не назад . Это поднимает очень важную тему в функциональном программировании: использование «формы» типа данных для получения «формы» вычислений. Если вы хотите обрабатывать элементы последовательно, односвязный список - это тип данных, который, когда вы используете его со структурной рекурсией, очень естественным образом предоставляет вам этот шаблон доступа. Если вы хотите использовать стратегию «разделяй и властвуй» для атаки на проблему, то древовидные структуры данных, как правило, поддерживают это очень хорошо.
Многие люди рано уходят из функционального программирования, поэтому они получают доступ к односвязным спискам, но не к более продвинутым базовым идеям.
источник
Потому что они хорошо работают с неизменяемостью. Предположим, у вас есть два неизменных списка,
[1, 2, 3]
и[10, 2, 3]
. Представленные в виде односвязных списков, где каждый элемент в списке является узлом, содержащим элемент и указатель на остальную часть списка, они будут выглядеть следующим образом:Видите, как
[2, 3]
порции идентичны? С изменчивыми структурами данных это два разных списка, потому что код, записывающий новые данные в одну из них, не должен влиять на код, использующий другую. Однако с неизменяемыми данными мы знаем, что содержимое списков никогда не изменится, и код не сможет записать новые данные. Таким образом, мы можем повторно использовать хвосты и иметь два списка, разделяющих часть их структуры:Поскольку код, использующий два списка, никогда не поменяет их, нам никогда не придется беспокоиться об изменениях в одном списке, влияющих на другой. Это также означает, что при добавлении элемента в начало списка вам не нужно копировать и создавать новый список.
Тем не менее, если вы попытаетесь представить
[1, 2, 3]
и[10, 2, 3]
как дважды связанные списки:Теперь хвосты больше не идентичны. Первый
[2, 3]
имеет указатель1
на заголовок, а второй - на10
. Кроме того, если вы хотите добавить новый элемент в заголовок списка, вы должны изменить предыдущий заголовок списка, чтобы он указывал на новый заголовок.Проблема множественных головок может быть потенциально решена, если каждый узел хранит список известных заголовков, а создание новых списков может изменить его, но тогда вам придется работать над поддержанием этого списка в циклах сборки мусора, когда версии списка с разными заголовками имеют разные времена жизни из-за использования в разных частях кода. Это добавляет сложности и накладных расходов, и в большинстве случаев это того не стоит.
источник
xs
конструкций1:xs
в одном месте и10:xs
в другой.Ответ @ sacundim в основном верен, но есть и другие важные идеи о компромиссе между языком и практическими требованиями.
Объекты и ссылки
Эти языки обычно предписывают (или предполагают) объекты, имеющие несвязанные динамические экстенты (или, на языке C, время жизни , хотя не совсем одно и то же из-за различий в значении объектов в этих языках, см. Ниже) по умолчанию, избегая ссылок первого класса ( например, указатели объектов в C) и непредсказуемое поведение в семантических правилах (например, неопределенное поведение ISO C, связанное с семантикой).
Кроме того, понятие (первоклассных) объектов в таких языках консервативно ограничительно: по умолчанию ничего «локативных» свойств не указывается и не гарантируется. Это полностью отличается в некоторых языках, подобных ALGOL, чьи объекты не имеют несвязанных динамических экстентов (например, в C и C ++), где объекты в основном означают некоторые виды «типизированного хранилища», обычно связанные с областями памяти.
Кодирование хранилища внутри объектов имеет некоторые дополнительные преимущества, такие как возможность добавлять детерминированные вычислительные эффекты в течение всего срока их службы, но это другая тема.
Проблемы моделирования структур данных
Без первоклассных ссылок односвязные списки не могут эффективно и переносимо моделировать многие традиционные (нетерпеливые / изменяемые) структуры данных из-за характера представления этих структур данных и ограниченных примитивных операций в этих языках. (Напротив, в C вы можете легко получить связанные списки даже в строго соответствующей программе .) И такие альтернативные структуры данных, как массивы / векторы, действительно имеют некоторые превосходные свойства по сравнению с односвязными списками на практике. Вот почему R 5 RS вводит новые примитивные операции.
Но существуют различия между типами векторов / массивов и списками с двойной связью. Массив часто предполагается с O (1) сложностью времени доступа и меньшими накладными расходами пространства, которые являются превосходными свойствами, не разделяемыми списками. (Хотя, строго говоря, ни один из них не гарантируется ISO C, но пользователи почти всегда ожидают этого, и никакая практическая реализация не нарушит эти неявные гарантии слишком очевидно.) OTOH, список с двойной связью часто делает оба свойства даже хуже, чем список с одной ссылкой тогда как обратная / прямая итерация также поддерживается массивом или вектором (вместе с целочисленными индексами) с еще меньшими издержками. Таким образом, двусвязный список не работает лучше в целом. Еще хуже, производительность по эффективности кэша и задержке при динамическом распределении памяти по спискам катастрофически хуже, чем производительность по массивам / векторам при использовании распределителя по умолчанию, предоставляемого базовой средой реализации (например, libc). Таким образом, без очень специфичной и «умной» среды выполнения, которая сильно оптимизирует создание таких объектов, типы массивов / векторов часто предпочтительнее связанных списков. (Например, при использовании ISO C ++ есть оговорка,
std::vector
должно быть предпочтительнееstd::list
по умолчанию.) Таким образом, введение новых примитивов для конкретной поддержки (дважды) связанных списков определенно не так выгодно, как поддержка структур массивов / векторных данных на практике.Справедливости ради, списки по-прежнему имеют некоторые специфические свойства лучше, чем массивы / векторы:
Однако эти свойства не слишком важны для языка со встроенной поддержкой односвязных списков, который уже может использоваться таким образом. Хотя все еще существуют различия, в языках с обязательными динамическими экстентами объектов (что обычно означает, что существует сборщик мусора, скрывающий висячие ссылки), аннулирование также может быть менее важным, в зависимости от намерений. Итак, единственными случаями, когда выигрывают двусвязные списки, могут быть:
Неизменность и алиасинг
На чистом языке, таком как Haskell, объекты неизменны. Объект схемы часто используется без мутаций. Такой факт позволяет эффективно повысить эффективность памяти за счет интернирования объектов - неявного совместного использования нескольких объектов с одинаковым значением на лету.
Это агрессивная стратегия оптимизации высокого уровня в дизайне языка. Однако это связано с проблемами реализации. Это фактически вводит неявные псевдонимы в базовые ячейки памяти. Это затрудняет анализ псевдонимов. В результате, вероятно, будет меньше возможностей для устранения издержек, связанных с ссылками не первого класса, даже пользователи никогда их не трогают. В таких языках, как Scheme, когда мутация не полностью исключена, это также мешает параллелизму. Это может быть хорошо на ленивом языке (у которого уже есть проблемы с производительностью, вызванные thunks в любом случае), все же.
Для программирования общего назначения такой выбор языкового дизайна может быть проблематичным. Но с некоторыми общими шаблонами функционального кодирования языки, кажется, все еще работают хорошо.
источник