?

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
Осознал, спасибо! Да, логично, после того как заменяемый элемент найден - хвост перебирать надо только чтоб найти тот, на который заменяем, а для нового списка можно прицепить как есть.

  • 1