Иммутабельность мешает иммутабельности

[_winnie]

Всё-таки мутабельность объектов в небольших пределах - иногда весьма облегчает написание алгоритмов. Это здорово, когда можно в небольшом обозримом участке кода создать объект A, перебросить на него указатели из другого уже созданного объекта B (который мы только что создали), и отложить заполнение полей A до того момента, когда они станут известны

Comments

[archaicos]

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

[_winnie]

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

[archaicos]

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

[buddy_ekb]

однако не рассказывайте про это адептам ФП - всё равно не поймут.
по существу вот:
http://kouzdra.livejournal.com/2684228.html
ещё есть дискуссия о "недоязыках":
https://github.com/facebook/immutable-js/issues/259

[_winnie]

По ссылке у kouzdra - не "черно-красное дерево", а "кусочек упрощенной балансировки в функции добавления", а самое сложное - это на самом деле удаление. Я там подробней прокомментировал.

[aamonster]

Ещё не вник в тему с деревом, но насчёт "создать указатель на незаполненный объект" - разве ленивость не для этого?

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

[_winnie]

Тредом ниже как раз обсудили ленивость.
Да, ленивость хоть и стоит дополнительных затрат, но в данном случае они пошли в дело, и позволили не запоминать копию списка целиком для переворачивания его создания.

[thedeemon]

Хм, в случае хаскеля тривиальное решение выглядит не так уж грустно:

change :: Eq a => a -> [a] -> [a]
change val (x:xs) = if x==val then last xs : xs
else x : change val xs
change val [] = []

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

[_winnie]

Угу, не так уж и плохо. Я даже переписал на C++, чтобы осознать что происходит - https://gist.github.com/dobrokot/0ebc9c9fbd55050dcee7

Почему хорошо с памятью - ленивость прячет "разрушающее копирование" и даёт возможность отложить создание указателей. Интересно получилось.

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

[thedeemon]

А что такое "разрушающее копирование" в данном случае?

Перевод прикольный получился. Я правильно понимаю, что лямбды тут продолжают жить в узлах списка и после срабатывания, держа счетчики ссылок? Как правильно поосвобождать замыкания - обнулить next_getter после использования?

[_winnie]

> А что такое "разрушающее копирование" в данном случае?
То, что cached_next нельзя объявить как const и инициализировать при создании.

> Как правильно поосвобождать замыкания - обнулить next_getter после использования?
Про это я не подумал, что можно так оптимизировать. Конкретно данный код и без этого работает без утечек памяти.

А если мы сделаем классический список чисел фиббоначи через zipWith с самим собой - то это не поможет.
Вот тут valgrind жалуется на утечку памяти: https://gist.github.com/dobrokot/0ebc9c9fbd55050dcee7
Чтобы их поосвобождать - нужен garbage collector, можно переписать на питоне/JavaScript/Java.

[thedeemon]

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

Решение на D:
http://dpaste.dzfl.pl/d35215cb3983
Тут change строит список мутабельно в один проход и без лишних выделений памяти, но возвращает его как immutable.
(не обошлось без одного каста внутри, но он не существенен)

[dmytrish]

Такое и в Хаскеле есть, впрочем. Смысл иммутабельности в Хаскеле не сама иммутабельность, а сохранение ссылочной прозрачности, поэтому Data.STRef и Control.Monad.ST вполне работают (тоже можно создать что-то внутри монады мутабельно, а потом вернуть результат как значение).