Как оформляются связи между immutable-данными?

Dasar

Какие есть паттерны для оформления связей при использовании immutable-данных?
Интересует, как обходится проблема, что для immutable-данных при обновления элемента необходимо обновить все ссылки, которые на этот элемент ссылаются.
пример


class World

{

   public World(Man вася, Man петя, Man маша){this.Вася = вася; this.Петя = петя; this.Маша = маша;}

   public readonly Man Вася;

   public readonly Man Петя;

   public readonly Man Маша;

}

class Man

{

   public Man(string name, Man chief)

   {

     this.Name = name;

     this.Chief = cheif;

   }

   public readonly string Name;

   public readonly Man Chief;

}



World ПоменятьНачальникаУВаси(World world, Man chief)

{ 

  //так недостаточно, потому что если Вася у кого-то уже в начальниках, то у этих людей будет старая версия Васи

  //return new World(new Man(world.Вася.Name, chief world.Петя, world.Маша);



  var oldВася = world.Вася;

  var newВася = new Man(world.Вася.Name, chief);

  return new World

  (

    newВася, 

    new Man(world.Петя.Name, world.Петя.chief == oldВася ? newВася : world.Петя.chief 

    new Man(world.Маша.Name, world.Маша.chief == oldВася ? newВася : world.Маша.chief)

   );

}

fktyf69

использовать публичные свойства с приватными сеттерами вместо readonly полей не подойдёт?

Dasar

не подходит.
Хочется оставаться в рамках парадигмы неизменяемости данных, т.к. это дает кучу полезных плюшек.

yroslavasako

А окасаки ты уже читал?

agaaaa

1. МС выпустила библиотеку с коллекцией разных неизменяемых структур данных. Посмотри её в NuGet. System Collections Immutable
2. Mans -> Men
3. Для построения коллекции иногда пользутся изменяемыми билдерами, как в случае со StringBuilder

Dasar

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

Dasar

убрал из примера коллекции, чтобы не отвлекали от основного вопроса.
ps
>> 1. МС выпустила библиотеку с коллекцией разных неизменяемых структур данных. Посмотри её в NuGet. System Collections Immutable
спасибо, посмотрю
>> 2. Mans -> Men
неудобно при машинной обработке кода

Hastya

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

Maurog

Какие есть паттерны для оформления связей при использовании immutable-данных?
Observer, COW, Proxy :grin:

Maurog

А окасаки ты уже читал?
да, но там про эффективность простых коллекций.
я вот не читал, неужели там нет описания реализаций? а все так нахваливают..что же там тогда интересного? :grin:

Dasar

Ты эту парадигму уже нарушил - у тебя связи изменяемые, со всеми вытекающими.
в смысле?

Dasar

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

Dasar

Observer, COW, Proxy
кстати, разбор этих паттернов для immutable где можно посмотреть?

Dasar

COW
это что такое?

Maurog

COW
это что такое?
http://en.wikipedia.org/wiki/Copy-on-write

Maurog

как обходится проблема, что для immutable-данных при обновления элемента необходимо обновить все ссылки
это делается путем обхода гетерогенной структуры и иммутабельной модификацией каждой составляющей
наиболее красиво это видно на примере хаскела
можно начать отсюда: http://hackage.haskell.org/package/base-4.4.1.0/docs/Data-T...

Dasar

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

6yrop

Моделируй связи реляционкой, и такой проблемы не будет:
 

    internal class Program

    {

        private static void Main(string[] args)

        {

            var маша = new Man(3, "Маша", 1);

            var world = ПоменятьНачальникаУВаси(

                new World(

                    вася: new Man(1, "Вася", 2

                    петя: new Man(2, "Петя", null

                    маша: маша

                маша);

            var men = world.Men.ToDictionary(_ => _.Id);

            foreach (var man in world.Men)

            {

                Console.WriteLine("{0} - {1}", 

                    man.Name, man.ChiefId.HasValue ? men[man.ChiefId.Value].Name : "");

            }

        }



        static World ПоменятьНачальникаУВаси(World world, Man chief)

        {

            return new World(

                вася: new Man(world.Вася.Id, world.Вася.Name, chief.Id 

                петя: world.Петя, 

                маша: world.Маша);

        }

    }



    class Man

    {

        public readonly int Id;

        public readonly string Name;

        public readonly int? ChiefId;



        public Man(int id, string name, int? chiefId)

        {

            Id = id;

            Name = name;

            ChiefId = chiefId;

        }

    }



    class World

    {

        public readonly Man Вася;

        public readonly Man Петя;

        public readonly Man Маша;



        public World(Man вася, Man петя, Man маша)

        {

            Вася = вася;

            Петя = петя;

            Маша = маша;

        }



        public IEnumerable<Man> Men

        {

            get

            {

                yield return Вася;

                yield return Петя;

                yield return Маша;

            }

        }

    }

Marinavo_0507

наиболее красиво это видно на примере хаскела
я про хаскель почти ничего не знаю, но не вижу в примере, как сделать чтоб не обходить всё дерево, а только те узлы, которые меняются?

Dasar

я про хаскель почти ничего не знаю, но не вижу в примере, как сделать чтоб не обходить всё дерево, а только те узлы, которые меняются?
Что такое "обходить только те узлы, которые меняются"?
ps
Корень проблемы изменения сложных данных с перекрестными ссылками как раз в том, что сложно предсказать какая часть дерева будет затронута при изменении одного элемента.

yroslavasako

отложить обход до того момента, как он понадобится. Отложить ещё больше, используя линзы. Надеяться на амортизированную сложность.

Marinavo_0507

Что такое "обходить только те узлы, которые меняются"?
ну там в примере я так понял предлагают запустить некий вариант map который поменяет все узлы
а у тебя задача: один узел меняется, надо побыстрее найти только те, которые на него ссылаются (ну и далее до корня)
сейчас кстати в моде файловые системы, которые примерно так устроены, вроде btrfs

Dasar

а у тебя задача: один узел меняется, надо побыстрее найти только те, которые на него ссылаются (ну и далее до корня)
нет других общих красивых решений, кроме fullscan-а
ps
"Некрасивые" решения - усложняют операцию создания дерева.
Чтобы менять точечно, элемент должен хранить "ссылки" на все ссылки, которые на него ссылаются. "Ссылки" должны быть в формате пути. Путь - это способ перейти от корня к элементу (прямой путь) или от элемента к корню(обратный путь).
Подвох в том, что пути меняются при операции композиции дерева: соответственно, операция композиции резко усложняется: требуя перестраивания путей, а не просто конкатенации двух элементов.
Если использовать обратные пути (через ссылку на родителя тогда операция конкатенации так же усложняется, т.к. если элемент вставляется во второе место дерева, то необходимо делать полную копию такого элемента (т.к у всех подэлементов меняются родители что убивает всю прелесть immutable.

yroslavasako

Насколько я помню на хаскел так и не вышло строить суффиксальное дерево за линейное время, если только не закамуфлировать императивный алгоритм и прямой доступ к памяти в монаду. Лучший алгоритм имеет скорость O(n*log(n такую же асимптоту можно легко получить из традиционного метода, заменив доступ по ссылкам O(1) на поиск по ключу O(log(n

Marinavo_0507

почему хранить обратные ссылки "некрасиво"? это вроде в ООП с его появления стандартная фишка
т.к. если элемент вставляется во второе место дерева, то необходимо делать полную копию такого элемента
зачем копию? несколько ссылок храни

Dasar

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

Marinavo_0507

ну не знаю поможет ли, но посмотри на btrfs
задачи навскидку те же, и уменьшение количества копирований очень важно
и код пишут настоящие мужики на суровом си, а не на каком-то гейском хаскеле

Dasar

ну не знаю поможет ли, но посмотри на btrfs
спасибо, посмотрю.
Оставить комментарий
Имя или ник:
Комментарий: