Как смоделировать циклическую ссылку между неизменяемыми объектами в C #?

24

В следующем примере кода у нас есть класс для неизменяемых объектов, который представляет комнату. Север, Юг, Восток и Запад представляют выходы в другие комнаты.

public sealed class Room
{
    public Room(string name, Room northExit, Room southExit, Room eastExit, Room westExit)
    {
        this.Name = name;
        this.North = northExit;
        this.South = southExit;
        this.East = eastExit;
        this.West = westExit;
    }

    public string Name { get; }

    public Room North { get; }

    public Room South { get; }

    public Room East { get; }

    public Room West { get; }
}

Итак, мы видим, что этот класс разработан с рефлексивной циклической ссылкой. Но поскольку класс неизменен, я застрял с проблемой «курица или яйцо». Я уверен, что опытные функциональные программисты знают, как справиться с этим. Как это можно сделать в C #?

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

ОБНОВИТЬ:

Вот рабочая реализация, основанная на ответе Майка Накиса относительно отложенной инициализации:

using System;

public sealed class Room
{
    private readonly Func<Room> north;
    private readonly Func<Room> south;
    private readonly Func<Room> east;
    private readonly Func<Room> west;

    public Room(
        string name, 
        Func<Room> northExit = null, 
        Func<Room> southExit = null, 
        Func<Room> eastExit = null, 
        Func<Room> westExit = null)
    {
        this.Name = name;

        var dummyDelegate = new Func<Room>(() => { return null; });

        this.north = northExit ?? dummyDelegate;
        this.south = southExit ?? dummyDelegate;
        this.east = eastExit ?? dummyDelegate;
        this.west = westExit ?? dummyDelegate;
    }

    public string Name { get; }

    public override string ToString()
    {
        return this.Name;
    }

    public Room North
    {
        get { return this.north(); }
    }

    public Room South
    {
        get { return this.south(); }
    }

    public Room East
    {
        get { return this.east(); }
    }

    public Room West
    {
        get { return this.west(); }
    }        

    public static void Main(string[] args)
    {
        Room kitchen = null;
        Room library = null;

        kitchen = new Room(
            name: "Kitchen",
            northExit: () => library
         );

        library = new Room(
            name: "Library",
            southExit: () => kitchen
         );

        Console.WriteLine(
            $"The {kitchen} has a northen exit that " +
            $"leads to the {kitchen.North}.");

        Console.WriteLine(
            $"The {library} has a southern exit that " +
            $"leads to the {library.South}.");

        Console.ReadKey();
    }
}
Рок Энтони Джонсон
источник
Это похоже на хороший пример для конфигурации и шаблона Builder.
Грег Бургхардт
Мне также интересно, должна ли комната быть отделена от планировки уровня или сцены, чтобы каждая комната не знала о других.
Грег Бургхардт
1
@RockAnthonyJohnson Я бы не назвал это рефлексивным, но это не уместно. Почему это проблема, хотя? Это чрезвычайно распространено. Фактически, так строятся почти все структуры данных. Подумайте о связанном списке или бинарном дереве. Все они - рекурсивные структуры данных, как и ваш Roomпример.
садовник
2
@RockAnthonyJohnson Неизменяемые структуры данных чрезвычайно распространены, по крайней мере, в функциональном программировании. Это , как вы определяете связанный список: type List a = Nil | Cons of a * List a. И бинарное дерево: type Tree a = Leaf a | Cons of Tree a * Tree a. Как видите, они оба ссылаются на себя (рекурсивно). Вот как вы бы определить номер: type Room = Nil | Open of {name: string, south: Room, east: Room, north: Room, west: Room}.
садовник
1
Если вам интересно, потратьте время на изучение Haskell или OCaml; это расширит ваш кругозор;) Также имейте в виду, что нет четкого разграничения между структурами данных и «бизнес-объектами». Посмотрите, насколько похожи определения вашего Roomкласса и a List в Haskell, который я написал выше.
садовник

Ответы:

10

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

Есть два способа, которыми я могу придумать (которые я использовал ранее), чтобы сделать это:

Используя две фазы

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

При моделировании реляционных баз данных вы можете столкнуться с точно такой же проблемой: одна таблица имеет внешний ключ, который указывает на другую таблицу, а другая таблица может иметь внешний ключ, который указывает на первую таблицу. Способ, которым это обрабатывается в реляционных базах данных, заключается в том, что ограничения внешнего ключа могут (и обычно) указываются с помощью дополнительного ALTER TABLE ADD FOREIGN KEYоператора, который отделен от CREATE TABLEоператора. Итак, сначала вы создаете все свои таблицы, затем добавляете ограничения внешнего ключа.

Разница между реляционными базами данных и тем, что вы хотите сделать, состоит в том, что реляционные базы данных продолжают разрешать ALTER TABLE ADD/DROP FOREIGN KEYоператоры в течение всего времени существования таблиц, в то время как вы, вероятно, установите флаг IamImmutable и откажетесь от любых дальнейших мутаций, как только будут реализованы все зависимости.

Использование ленивой инициализации

Вместо ссылки на зависимость вы передаете делегат, который при необходимости вернет ссылку на зависимость. Как только зависимость извлечена, делегат больше никогда не вызывается.

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

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

Вы даже можете создать универсальный класс «ленивых ссылок», который реализует это, так что вам не нужно повторно реализовывать его для каждого из ваших членов.

Вот такой класс написан на Java, вы легко можете переписать его на C #

(Мой Function<T>как Func<T>делегат C #)

package saganaki.util;

import java.util.Objects;

/**
 * A {@link Function} decorator which invokes the given {@link Function} only once, when actually needed, and then caches its result and never calls it again.
 * It behaves as if it is immutable, which includes the fact that it is thread-safe, provided that the given {@link Function} is also thread-safe.
 *
 * @param <T> the type of object supplied.
 */
public final class LazyImmutable<T> implements Function<T>
{
    private static final boolean USE_DOUBLE_CHECK = false; //TODO try with "double check"
    private final Object lock = new Object();
    @SuppressWarnings( "FieldAccessedSynchronizedAndUnsynchronized" )
    private Function<T> supplier;
    @SuppressWarnings( "FieldAccessedSynchronizedAndUnsynchronized" )
    private T value;

    /**
     * Constructor.
     *
     * @param supplier the {@link Function} which will supply the supplied object the first time it is needed.
     */
    public LazyImmutable( Function<T> supplier )
    {
        assert supplier != null;
        assert !(supplier instanceof LazyImmutable);
        this.supplier = supplier;
        value = null;
    }

    @Override
    public T invoke()
    {
        if( USE_DOUBLE_CHECK )
        {
            if( supplier != null )
                doCheck();
            return value;
        }

        doCheck();
        return value;
    }

    private void doCheck()
    {
        synchronized( lock )
        {
            if( supplier != null )
            {
                value = supplier.invoke();
                supplier = null;
            }
        }
    }

    @Override
    public String toString()
    {
        if( supplier != null )
            return "(lazy)";
        return Objects.toString( value );
    }
}

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

Майк Накис
источник
1
Майк, ты великолепен. Я обновил исходный пост, чтобы включить реализацию, основанную на том, что вы опубликовали о ленивой инициализации.
Рок Энтони Джонсон
1
Библиотека .Net предоставляет ленивую ссылку, метко названную Lazy <T>. Как чудесно! Я узнал об этом из ответа на обзор кода, который я разместил на codereview.stackexchange.com/questions/145039/…
Рок Энтони Джонсон,
16

Ленивый шаблон инициализации в ответе Майка Накиса прекрасно работает для одноразовой инициализации между двумя объектами, но становится громоздким для нескольких взаимосвязанных объектов с частыми обновлениями.

Намного проще и удобнее управлять связями между комнатами вне самих комнатных объектов, что-то вроде ImmutableDictionary<Tuple<int, int>, Room>. Таким образом, вместо создания циклических ссылок, вы просто добавляете одну легко обновляемую одностороннюю ссылку на этот словарь.

Карл Билефельдт
источник
Имейте в виду, речь шла об неизменных объектах, поэтому обновлений нет.
Рок Энтони Джонсон
4
Когда люди говорят об обновлении неизменяемых объектов, они имеют в виду создание нового объекта с обновленными атрибутами и обращение к этому новому объекту в новой области вместо старого объекта. Впрочем, каждый раз говорить об этом немного утомительно.
Карл Билефельдт
Карл, пожалуйста, прости меня. Я все еще новичок в функциональных принципах, хаха.
Рок Энтони Джонсон
2
Это правильный ответ. Циркулярные зависимости, как правило, должны быть нарушены и переданы третьей стороне. Это гораздо проще, чем программирование сложной системы сборки-замораживания изменяемых объектов, которые становятся неизменяемыми.
Бенджамин Ходжсон
Если бы я мог дать этому еще несколько +1 ... Неизменный или нет, без "внешнего" хранилища или индекса (или чего- либо еще ), правильно подключить все эти комнаты было бы излишне сложно. И это не запрещает Roomиз появляясь , чтобы эти отношения; но они должны быть получателями, которые просто читают из индекса.
svidgen
12

Способ сделать это в функциональном стиле - узнать, что вы на самом деле строите: ориентированный граф с помеченными ребрами.

Room library = new Room("Library");
Room ballroom = new Room("Ballroom");
Thing chest = new Thing("Treasure chest");
Thing book = new Thing("Ancient Tome");
Dungeon dungeon = Dungeon.Empty
  .WithRoom(library)
  .WithRoom(ballroom)
  .WithThing(chest)
  .WithThing(book)
  .WithPassage("North", library, ballroom)
  .WithPassage("South", ballroom, library)
  .WithContainment(library, chest)
  .WithContainment(chest, book);

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

Эрик Липперт
источник
1
Я изучал ориентированные графы и беглых строителей (и DSL). Я могу видеть, как это могло бы создать ориентированный граф, но я впервые увидел две связанные идеи. Я пропустил книгу или блог? Или это создает ориентированный граф просто потому, что это решает проблему вопросов?
Candied_Orange
@CandiedOrange: это эскиз того, как может выглядеть API. На самом деле построение структуры данных неизменяемого ориентированного графа, лежащей в ее основе, потребует некоторой работы, но это не сложно. Неизменяемый ориентированный граф - это просто неизменный набор узлов и неизменный набор (начало, конец, метка) троек, поэтому его можно свести к композиции уже решенных задач.
Эрик Липперт
Как я уже сказал, я изучил как DSL, так и ориентированные графы. Я пытаюсь выяснить, прочитали ли вы или написали что-то, что соединяет их вместе, или вы просто собрали их вместе, чтобы ответить на этот конкретный вопрос. Если вы знаете о чем-то, что объединяет их, я буду рад, если вы укажете мне на это.
candied_orange
@CandiedOrange: Не особенно. Много лет назад я написал серию блогов на неизменном неориентированном графике для решения проблемы судоку. Недавно я написал серию блогов о проблемах объектно-ориентированного проектирования для изменчивых структур данных в области волшебников и подземелий.
Эрик Липперт
3

Цыпленок и яйцо это правильно. Это не имеет смысла в C #:

A a = new A(b);
B b = new B(a);

Но это делает:

A a = new A();
B b = new B(a);
a.setB(b);

Но это означает, что А не является неизменным!

Вы можете обмануть:

C c = new C();
A a = new A(c);
B b = new B(c);
c.addA(a);
c.addB(b);

Это скрывает проблему. Конечно, A и B имеют неизменное состояние, но они относятся к чему-то, что не является неизменным. Что может легко победить цель сделать их неизменными. Я надеюсь, что C, по крайней мере, настолько потокобезопасен, насколько вам нужно.

Существует шаблон, называемый заморозка-оттаивание:

A a = new A();
B b = new B(a);
a.addB(b);
a.freeze();

Теперь «а» является неизменным. «А» не есть, а «есть». Почему это нормально? До тех пор, пока ничто не знает об «а» до того, как оно замерзнет, ​​кого это волнует?

Есть метод thaw (), но он никогда не меняет «a». Это делает изменчивую копию «а», которая может быть обновлена, а затем заморожена.

Недостатком этого подхода является то, что класс не обеспечивает неизменность. Следующая процедура есть. Вы не можете сказать, является ли это неизменным от типа.

Я действительно не знаю идеальный способ решить эту проблему в C #. Я знаю способы скрыть проблемы. Иногда этого достаточно.

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

candied_orange
источник
+1 за знакомство с новым паттерном. Впервые я услышал о замораживании-оттаивании.
Рок Энтони Джонсон
a.freeze()может вернуть ImmutableAтип. которые делают его в основном образцом строителя.
Брайан Чен
@BryanChen, если вы сделаете это, то останетесь bсо ссылкой на старый изменяемый файл a. Идея заключается в том , что a и bдолжно указывать на неизменных версии друг от друга , прежде чем выпустить их к остальной части системы.
candied_orange
@RockAnthonyJohnson Это также то, что Эрик Липперт назвал неизменностью эскимо .
Пятно,
1

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

Я думаю, что здание должно знать, где находятся комнаты. Если комната действительно должна знать своих соседей, передайте ей INeigbourFinder.

tymtam
источник