Обновление вложенных неизменяемых структур данных

Ответ 1

Я задал аналогичный вопрос, но про haskell: Есть ли иконка Haskell для обновления вложенной структуры данных?

В превосходных ответах упоминается концепция, известная как функциональные линзы.

К сожалению, я не знаю, что такое пакет или если он существует даже для F #.

Обновление: два знающих F # -ists (F # -ers? F # as?) оставили полезные ссылки об этом в комментариях, поэтому я отправлю их здесь:

• @TomasPetricek предложил FSharpX и этот сайт, описывающий его

• @RyanRiley предоставил ссылку для пакета

Удивительно, что эти двое парней нашли время, чтобы прочитать мой ответ, прокомментировать и улучшить его, поскольку они оба являются разработчиками FSharpX!

Больше посторонней информации: мне было интересно выяснить, как это сделать с помощью функций Clojure assoc-in и update-in, которые доказали мне, что это возможно на функциональных языках! Разумеется, динамическая типизация Clojure делает ее проще, чем в Haskell/F #. Я полагаю, решение Haskell предполагает шаблонизацию.

Ответ 2

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

open FSharpx

type Monster = {
    Awake: bool
} with 
    static member awake =
        { Get = fun (x: Monster) -> x.Awake
          Set = fun v (x: Monster) -> { x with Awake = v } }

type Room = {
    Locked: bool
    Monsters: Monster list
} with
    static member locked = 
        { Get = fun (x: Room) -> x.Locked
          Set = fun v (x: Room) -> { x with Locked = v } }
    static member monsters = 
        { Get = fun (x: Room) -> x.Monsters
          Set = fun v (x: Room) -> { x with Monsters = v } }

type Level = {
    Illumination: int
    Rooms: Room list
} with
    static member illumination = 
        { Get = fun (x: Level) -> x.Illumination
          Set = fun v (x: Level) -> { x with Illumination = v } }
    static member rooms = 
        { Get = fun (x: Level) -> x.Rooms
          Set = fun v (x: Level) -> { x with Rooms = v } }

type Dungeon = {
    Levels: Level list
} with
    static member levels =
        { Get = fun (x: Dungeon) -> x.Levels 
          Set = fun v (x: Dungeon) -> { x with Levels = v } }
    static member print (d: Dungeon) = 
        d.Levels 
        |> List.iteri (fun i e -> 
            printfn "Level %d: Illumination %d" i e.Illumination
            e.Rooms |> List.iteri (fun i e ->
                let state = if e.Locked then "locked" else "unlocked"
                printfn "  Room %d is %s" i state
                e.Monsters |> List.iteri (fun i e ->
                    let state = if e.Awake then "awake" else "asleep"
                    printfn "    Monster %d is %s" i state)))

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

Теперь, чтобы сгенерировать образцы данных. Я думаю, что { Monster.Awake = true } более descive, чем new Monster(true). Если вы хотите использовать классы, я бы назвал этот параметр явно, например. Monster(awake: true)

// generate test dungeon
let m1 = { Monster.Awake = true }
let m2 = { Monster.Awake = false }
let m3 = { Monster.Awake = true }
let m4 = { Monster.Awake = false }
let m5 = { Monster.Awake = true }
let m6 = { Monster.Awake = false }
let m7 = { Monster.Awake = true }
let m8 = { Monster.Awake = false }

let r1 = { Room.Locked = true;  Monsters = [m1; m2] }
let r2 = { Room.Locked = false; Monsters = [m3; m4] }
let r3 = { Room.Locked = true;  Monsters = [m5; m6] }
let r4 = { Room.Locked = false; Monsters = [m7; m8] }

let l1 = { Level.Illumination = 100; Rooms = [r1; r2] }
let l2 = { Level.Illumination = 50;  Rooms = [r3; r4] }

let dungeon = { Dungeon.Levels = [l1; l2] }
Dungeon.print dungeon

Теперь идет интересная часть: создание линз для обновления монстров для всех комнат для определенного уровня в подземелье:

open FSharpx.Lens.Operators

let mapMonstersOnLevel nLevel f =
    Dungeon.levels >>| Lens.forList nLevel >>| Level.rooms >>| Lens.listMap Room.monsters
    |> Lens.update (f |> List.map |> List.map)

// toggle wake status of all monsters
let dungeon1 = dungeon |> mapMonstersOnLevel 0 (Monster.awake.Update not)
Dungeon.print dungeon1

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

// remove monsters that are asleep 
// which are in locked rooms on levels where illumination < 100 
// and unlock those rooms

let unlock = Room.locked.Set false
let removeAsleepMonsters = Room.monsters.Update (List.filter Monster.awake.Get)

let removeAsleepMonsters_unlock_rooms = List.mapIf Room.locked.Get (unlock >> removeAsleepMonsters)

let isLowIllumination = Level.illumination.Get >> ((>)100)
let removeAsleepMonsters_unlock_level = Level.rooms.Update removeAsleepMonsters_unlock_rooms
let removeAsleepMonsters_unlock_levels = List.mapIf isLowIllumination removeAsleepMonsters_unlock_level

let dungeon2 = dungeon |> Dungeon.levels.Update removeAsleepMonsters_unlock_levels
Dungeon.print dungeon2

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

Но что более важно, поскольку Update - это Get, за которым следует функция, за которой следует Set, это не так эффективно, как ваш код, когда дело доходит до списков обработки: Update в Lens.forList сначала получает n-й элемент в список, который является операцией O (n).

Подводя итог:

Плюсы:

• Очень краткий.
• Включает стиль с нулевой точкой.
• Код, включающий объективы, обычно не обращается к представлению типа источника (это может быть класс, запись, одноразовый DU, словарь, это не имеет значения).

Минусы:

• Может быть неэффективным для некоторых случаев в текущей реализации.
• Из-за нехватки макросов требуется некоторый шаблон.

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

Я передал этот код в репозиторий FSharpx: https://github.com/fsharp/fsharpx/commit/136c763e3529abbf91ad52b8127ce11cbb3dff28

Ответ 3

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

// Types
type Monster = {
    Awake: bool
    }
    with override x.ToString() =
            if x.Awake then "awake" else "asleep"
type Room = {
    Locked: bool;
    Monsters: Monster list
    }
    with override x.ToString() =
            let state = if x.Locked then "locked" else "unlocked"
            state + "\n" + (x.Monsters |> List.mapi (fun i m -> sprintf "    Monster %d is %s" i (string m)) |> String.concat "\n")

type Level = {
    Illumination : int;
    Rooms : Room list
    }
    with override x.ToString() =
              (string x.Illumination) + "\n" + (x.Rooms |> List.mapi (fun i r -> sprintf "  Room %d is %s" i (string r)) |> String.concat "\n")

type Dungeon = {
    Levels: Level list;
    }
    with override x.ToString() =
            x.Levels |> List.mapi (fun i l -> sprintf "Level %d: Illumination %s" i (string l)) |> String.concat "\n"

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

/// Utility functions
let updateMonster (m: Monster) a =
    {m with Awake = a}

let updateRoom (r: Room) l monstersFunc =
    {   Locked = l; 
        Monsters = r.Monsters |> monstersFunc}    

let updateLevel (l: Level) il roomsFunc = 
    {Illumination = il; Rooms = l.Rooms |> roomsFunc}

let updateDungeon (d: Dungeon) levelsFunc =
    {d with Levels = d.Levels |> levelsFunc}


/// Update functions
let mapMonstersOnLevel (d: Dungeon) nLevel =
    let monstersFunc = List.map (fun m -> updateMonster m (not m.Awake))
    let roomsFunc = List.map (fun r -> updateRoom r r.Locked monstersFunc)
    let levelsFunc = List.mapi (fun i l -> if i = nLevel then updateLevel l l.Illumination roomsFunc else l)
    updateDungeon d levelsFunc

let removeSleptMonsters (d: Dungeon) =
    let monstersFunc = List.filter (fun m -> m.Awake)
    let roomsFunc = List.map (fun r -> if r.Locked then updateRoom r false monstersFunc else r)
    let levelsFunc = List.map (fun l -> if l.Illumination < 100 then updateLevel l l.Illumination roomsFunc else l)
    updateDungeon d levelsFunc

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

Ответ 4

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

Ответ 5

Я реализовал библиотеку объективов на С# через отражение. Ядром библиотеки является эта функция

/// <summary>
/// Perform an immutable persistent set on a sub
/// property of the object. The object is not
/// mutated rather a copy of the object with
/// the required change is returned.
/// </summary>
/// <typeparam name="ConvertedTo">type of the target object</typeparam>
/// <typeparam name="V">type of the value to be set</typeparam>
/// <param name="This">the target object</param>
/// <param name="names">the list of property names composing the property path</param>
/// <param name="value">the value to assign to the property</param>
/// <returns>A new object with the required change implemented</returns>
private static T Set<T, V>
    (this T This, List<string> names, V value)
    where T : class, Immutable
{
    var name = names.First();
    var rest = names.Skip(1).ToList();
    if (names.Count == 1)
    {
        var copy = This.ShallowClone();
        copy.SetPrivatePropertyValue(names.First(), value);
        return copy as T;
    }
    else
    {
        var copy = This.ShallowClone();
        var subtree = copy
            .GetPrivatePropertyValue<Immutable>(name)
            .Set(rest, value);

        copy.SetPrivatePropertyValue(names.First(), subtree);
        return copy as T;
    }
}

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

public static Maybe<T> MaybeSet<T,V>
    (this T This, Expression<Func<T, V>> prop, V value)
    where T : class, Immutable
{
    if (!EqualityComparer<V>.Default.Equals(This.Get(prop.Compile()),value))
    {
        var names = ReactiveUI.Reflection.ExpressionToPropertyNames(prop).ToList();
        return This.Set(names, value).ToMaybe();
    }
    else
    {
        return None<T>.Default;
    }
}

который позволяет использовать более безопасную нотацию естественного типа с использованием выражений LINQ.

foo = foo.Set(f=>f.A.B.C, 10);

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

class A : Immutable
{
    public int P { get; private set; }
    public B B { get; private set; }
    public A(int p, B b)
    {
        P = p;
        B = b;
    }
}

class B : Immutable
{
    public int P { get; private set; }
    public C C { get; private set; }
    public B(int p, C c)
    {
        P = p;
        C = c;
    }
}

class C : Immutable
{
    public int P { get; private set; }
    public C(int p)
    {
        P = p;
    }
}


namespace Utils.Spec
{
    public class ImmutableObjectPatternSpec : IEnableLogger
    {
        [Fact]
        public void SetterSpec()
        {
            var a = new A
                ( p:10
                , b: new B
                    ( p: 20
                    , c : new C(30)));

            var a_ = a.Set(p => p.B.C.P, 10);

            a.Should().NotBe(a_);
            a.B.C.P.Should().Be(30);
            a_.B.C.P.Should().Be(10);
        }

        [Fact]
        public void StringListGettersShouldWork()
        {
            var a = new A
                ( p:10
                , b: new B
                    ( p: 20
                    , c : new C(30)));

            var a_ = a.Set(p => p.B.C.P, 10);

            a_.Get(p=>p.B.C.P).Should().Be(10);

        }




    }
}

Возможно, линзы, основанные на отражении, уменьшат плиту котла в F #. Может быть производительность может быть улучшена с помощью кэширования аксессуаров или, возможно, IL поколения.