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

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

Вопрос: Каким был бы идиоматический или рекомендуемый способ реализации двусвязного списка (или другой двусвязной или круговой структуры данных) и операций с ним на языке, который в основном поддерживает и поддерживает неизменные структуры данных (Haskell, Clojure и т. Д.) ? В частности, как использовать обновления на месте, которые формально запрещены языком?

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

Означает ли это, что для таких задач неизменяемые данные просто неуместны, а функциональные декларативные языки без «нативной» поддержки изменяемых данных не так хороши, как императивные? Или есть какой-то хитрый обходной путь?

PS Я нашел несколько статей и презентаций на эту тему в Интернете, но с трудом следил за ними, хотя я думаю, что ответ на этот вопрос не должен занимать более одного абзаца и, возможно, диаграммы ... Я имею в виду, если есть нет «функционального» решения этой проблемы, ответ, вероятно, «использовать C». Если есть, то насколько это может быть сложно?

Смежные вопросы

• «Структуры данных в функциональном программировании» . Мой конкретный вопрос об использовании обновлений на месте вместо неэффективных альтернатив здесь не обсуждается.

• «Внутренняя мутация постоянных структур данных» . Здесь акцент, кажется, делается на низкоуровневой реализации на неопределенном языке, в то время как мой вопрос касается правильного выбора языка (функционального или иного) и возможных идиоматических решений в функциональных языках.

Соответствующие цитаты

Чисто функциональные языки программирования позволяют выразить многие алгоритмы очень кратко, но есть несколько алгоритмов, в которых обновляемое состояние на месте, кажется, играет решающую роль. Для этих алгоритмов чисто функциональные языки, в которых отсутствует обновляемое состояние, по своей природе оказываются неэффективными ( [Ponder, McGeer and Ng, 1988] ).

- Джон Лончбери и Саймон Пейтон Джонс, « Ленивые потоки функционального состояния» (1994), а также Джон Лончбери и Саймон Пейтон Джонс, « Штат в Хаскелле» (1995). Эти документы вводят STконструктор монадического типа в Haskell.

Могут быть и другие эффективные неизменяемые структуры данных, которые соответствуют вашей конкретной задаче, но не такие общие, как двусвязный список (который, к сожалению, подвержен параллельным ошибкам модификации из-за своей изменчивости). Если вы укажете свою проблему более узко, такую ​​структуру, вероятно, можно найти.

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

Еще одна полезная конструкция - молния . (Самое смешное в том, что сигнатура типа для молнии линзы является производной математической производной от сигнатуры типа структуры.)

Вот несколько ссылок.

• Простое объяснение молнии

• Глава о молниях из "Learn you a Haskell"

• Введение в линзы в Scala (слайды)

• Базовое лицензирование
• Линзы в функциональном программировании

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

Я бы предложил исследовать использование программной транзакционной памяти в качестве пути продвижения вперед. Помимо обеспечения эффективного способа реализации изменяемых структур, он также предоставляет очень полезные гарантии безопасности потоков. См. Описание модуля по адресу https://hackage.haskell.org/package/stm и обзор вики по адресу https://wiki.haskell.org/Software_transactional_memory .