?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
Иммутабельность мешает иммутабельности
nyaload
_winnie
Всё-таки мутабельность объектов в небольших пределах - иногда весьма облегчает написание алгоритмов. Это здорово, когда можно в небольшом обозримом участке кода создать объект A, перебросить на него указатели из другого уже созданного объекта B (который мы только что создали), и отложить заполнение полей A до того момента, когда они станут известны. Но в иммутабельном языке - невозможно создать объект, пока мы не знаем все параметры для его создания, и это дико мешает при переложении известных алгоритмов на такой язык. Нужно вводить дополнительные структуры данных, чтобы поменять порядок создания объектов A и B, так как мы в случае иммутабельности не можем создать A, а потом провести из него указатель в B.

Например, пусть пишем персистентное дерево. Персистентное - это значит слегка изменённые клоны этого дерева создаются легко, и при этом мы не теряем оригинал. Как дерево директорий файловой системы в системе контроля версий - мы при модификации этого дерева и файлов в нём не разрушаем информацию о предыдущих версиях (подробней о сортах персистентности).
То есть, если нам надо создавать персистентные структуры данных, то с одной стороны в иммутабельном ЯП и не можем сделать не-персистентные, что типа должно помогать. С другой стороны - он мешает реализовать промежуточную постройку таких структур в недостроенном состоянии, требуя построить шпиль башни до её фундамента, и запрещая все иные способы постройки.

Это, например, мешает переписывать из википедии алгоритм персистентного красно-черного дерева на такой язык. Там есть подзадача, похожая на такую: в односвязном списке поменять значение ноды с удаляемым значением где-то внутри списка на значение из ноды в конце списка. Список персистентный, поэтому "поменять" означает "создать клон с нужным изменением".
В языке, где можно менять значения полей объекта - всё тривиально, решается в один проход от начала до конца списка.
Идем от начала до нужной внутренней ноды списка, пока идём - создаем дубликаты проходимых нод. Когда нашли нужную ноду - запоминаем указатель на её дубликат, доходим до конца списка, копируем значение в созданный дубликат. Лишней памяти, при условии что нам надо сохранить и старый список (персистентность в copy-on-write её варианте) - не тратится.


В случае же иммутабельного языка программирования - нельзя начать создавать новый список, пока мы полностью не разобрались, какое значение положить в его середине.
Так как пока не найдена нужная нода с изменяемым значением - мы не можем создать все ноды перед перед ней, включая первую. А ноду с изменяемым значением мы не можем создать, так как не знаем новое значение из конца списка.
Получается, что мы тратим дополнительные мозги на изобретение того, как же перевернуть задом наперед заполнение списка, и тратим на это память (иногда неявно, на параметры глубокой рекурсии).


  • 1
А готового дерева нет?

Мне для самообразования. 10 лет использую std::map/TreeMap, и боялся смотреть внутрь.

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

Так же в тех вариантах персистентных rb-деревьев не для Haskell - жуткие простыни разбора случаев, а мне удалось написать более компатно:
Например, функция удаления ноды из дерева.
мой вариант - http://pastebin.com/T0vu1Sw8 (а комменты в коде - ведут на картинки из википедии, они уже мне помогли пофиксать опечатки).

вариант который быстро находится гуглем по запросам
"js persistent rb tree" - http://pastebin.com/FzvG3nJ8 , взято с https://github.com/mikolalysenko/functional-red-black-tree/blob/master/rbtree.js )
"java persistent rb tree" http://pastebin.com/qZJPCupy , взято с http://wiki.edinburghhacklab.com/PersistentRedBlackTreeSet
Вариант с Хаскелла - его мне сложно переложить на другой язык, так чтобы получилось не ужасно, вот он - https://hackage.haskell.org/package/RBTree-0.0.5/docs/src/Data-Tree-RBTree.html#deleteOrdList
В Хаскелле слишком легко определять в 10 букв много крошечных абстраций (типа topMostZip), которые сильно раздуваются при прямолинейном переписывании





Edited at 2015-11-04 10:19 pm (UTC)

Я лет 10-15 назад писал RB и AVL. RB жутковато, конечно, но вроде никакой магии. Как оно пишется функционально-иммутабельно (а уж тем более что из этого делает компилятор) никогда не задумывался.

  • 1