Чисто функциональные структуры данных с копированием при записи?

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

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

Допустим, foo — это карта.

bar = foo.clone()

Ничего из структуры foo (например, дерево) пока не копируется. Однако с этого момента bar рассматривается как копия, и никакие изменения не могут передаваться обратно в `foo'.

baz = bar[someKey]
baz.modifyInSomeWay()

В настоящее время

  • создается новый объект, который является модифицированной копией baz.
  • bar заменяется новой картой, содержащей новый baz (возможно, сохраняя часть структуры foo).
  • foo не затронут.

Но если мы тогда сделаем...

baz.modifyAgain()

...baz можно просто изменить, потому что у нас есть последняя версия. bar менять не нужно.

Все это требует хранения некоторой информации о версии foo и bar, увеличения ее на foo.clone() и передачи каким-то образом на baz (сделав ее прокси-объектом?).

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

Это немного похоже на прототипы JavaScript, но в большей степени позволяет изменениям распространяться вверх. Я думаю, это будет что-то вроде системы контроля версий.

  • Было ли это сделано и в какой степени?
  • Это хорошая идея? Если нет, то есть ли способ его сохранить?
  • Как это могло быть реализовано? Я подумывал о том, чтобы создать его на основе какого-нибудь языка высокого уровня с сборщиком мусора, такого как Python.

python immutability functional-programming copy-on-write
person hmp    schedule 04.09.2009    source источник
comment
вероятно, pyrsistent — это то, что вы ищете   -  person CAMOBAP    schedule 24.05.2017

Ответы (3)


arrow_upward
8
arrow_downward

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

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

Постоянные структуры данных могут иметь значительные накладные расходы, но если у вас есть очень эффективное распределение небольших объектов (подходит JVM GC), они могут быть очень практичными - в лучшем случае так же быстро, как и изменяемый эквивалент, обеспечивая сохранение только за счет используемая память - которая может быть намного меньше, чем полная копия при каждом обновлении.

В зависимости от вашего языка вы, вероятно, обнаружите, что желаемый синтаксис трудно реализовать без перегрузки оператора для присваивания. Lvalues ​​(изменяемые ссылки) в C++ определенно требуют непостоянной семантики.

person Jonathan Graehl    schedule 04.09.2009

arrow_upward
0
arrow_downward

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

например в Скала

class ImmutableData{
   def doStuff(blah : Blah) : ImmutableData = implementation
}

class MutableData(var wrapped : ImmutableData){
  def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); } 
}

Конечно, это означает, что вам нужно сделать две версии интерфейса, но семантика намного разумнее.

person DRMacIver    schedule 05.09.2009
comment
Верно, но это означает обновление всего остального вручную — я не могу использовать такие MutableData ни в какой другой неизменяемой структуре данных. - person hmp; 05.09.2009
comment
Я не понимаю. Если вы хотите использовать его неизменно, вы можете получить версию моментального снимка, просто развернув его. - person DRMacIver; 07.09.2009

arrow_upward
0
arrow_downward

<сильный>1. Было ли это сделано и в какой степени?

Да, см., например, qt5 неявный обмен.

<сильный>2. Это хорошая идея? Если нет, есть ли способ сохранить его?

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

<сильный>3. Как это могло быть реализовано? Я подумывал о том, чтобы создать его на основе какого-нибудь языка высокого уровня, предназначенного для сборщика мусора, например Python.

Один из способов — использовать подсчет ссылок, как в qt (см. описание здесь). Для его реализации потребуется либо перегрузка оператора присваивания, либо явный вызов метода (например, bar = foo.clone(), но он может быть хрупким, что произойдет, если кто-то забудет вызвать clone и просто сделает bar = foo?), поэтому подсчет можно сохранить.

Другая возможность создать прокси-объект, как вы сказали. См., например, pycow (реализация Python).

person malbarbo    schedule 10.05.2016