更新嵌套的不可变数据结构

Question

我想更新一个嵌套的、不可变的数据结构（我附上了一个虚构游戏的小例子），我想知道是否有更加优雅的方法可以实现。

每当地牢内部发生改变时，我们都需要一个新的地牢。因此，我给它了一个通用的更新成员。为了在一般情况下使用这个最好的方法，我为每个嵌套指定了处理函数，然后将组合函数传递给更新成员。

然后，对于真正常见的情况（比如将地图应用到特定级别的所有怪物上），我提供了额外的成员（Dungeon.MapMonstersOnLevel）。

整个过程是有效的，只是我想知道是否有人能想到更好的方法。

谢谢！

// types
type Monster(awake : bool) = 
    member this.Awake = awake

type Room(locked : bool, monsters : Monster list) = 
    member this.Locked = locked
    member this.Monsters = monsters

type Level(illumination : int, rooms : Room list) = 
    member this.Illumination = illumination
    member this.Rooms = rooms

type Dungeon(levels : Level list) = 
    member this.Levels = levels

    member this.Update levelFunc = 
        new Dungeon(this.Levels |> levelFunc)

    member this.MapMonstersOnLevel (f : Monster -> Monster) nLevel =
        let monsterFunc = List.map f
        let roomFunc = List.map (fun (room : Room) -> new Room(room.Locked, room.Monsters |> monsterFunc))
        let levelFunc = List.mapi (fun i (level : Level) -> if i = nLevel then new Level(level.Illumination, level.Rooms |> roomFunc) else level)
        new Dungeon(this.Levels |> levelFunc)

    member this.Print() = 
        this.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)))

// generate test dungeon
let m1 = new Monster(true)
let m2 = new Monster(false)
let m3 = new Monster(true)
let m4 = new Monster(false)
let m5 = new Monster(true)
let m6 = new Monster(false)
let m7 = new Monster(true)
let m8 = new Monster(false)
let r1 = new Room(true, [ m1; m2 ])
let r2 = new Room(false, [ m3; m4 ])
let r3 = new Room(true, [ m5; m6 ])
let r4 = new Room(false, [ m7; m8 ])
let l1 = new Level(100, [ r1; r2 ])
let l2 = new Level(50, [ r3; r4 ])
let dungeon = new Dungeon([ l1; l2 ])
dungeon.Print()

// toggle wake status of all monsters
let dungeon1 = dungeon.MapMonstersOnLevel (fun m -> new Monster(not m.Awake)) 0
dungeon1.Print()

// remove monsters that are asleep which are in locked rooms on levels where illumination < 100 and unlock those rooms
let monsterFunc2 = List.filter (fun (monster : Monster) -> monster.Awake)
let roomFunc2 = List.map(fun (room : Room) -> if room.Locked then new Room(false, room.Monsters |> monsterFunc2) else room)
let levelFunc2 = List.map(fun (level : Level) -> if level.Illumination < 100 then new Level(level.Illumination, level.Rooms |> roomFunc2) else level)
let dungeon2 = dungeon.Update levelFunc2
dungeon2.Print()

- bknotic

---

你考虑过使用记录或单例联合类型吗？ - Ramon Snir

@RamonSnir：我尝试在下面的pad答案中解释自己。 - bknotic

Answer 1

以下是使用FSharpx定义的lenses（镜片）的相同代码。

正如其他答案所指出的那样，这里使用记录很方便；它们免费提供了结构等式和其他功能。

我还将属性的相应lenses附加为静态成员；您也可以在模块中或作为松散函数定义它们。 在此处，我更喜欢使用静态成员，因为在实际用途中它就像一个模块。

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 }比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

第二个地下城中，我也使用了 lens，但没有使用 lens 组合。这是一种由小型组合函数定义的 DSL（一些函数来自于 lens）。也许有更简洁的方式用 lens 表达它，但我还没想出来。

// 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

这里我有意过度使用了镜头和pointfree，部分是为了展示它可能是什么样子的。有些人可能不喜欢它，认为它不符合惯用法或不够清晰。也许是这样，但这是另一个工具，根据您的上下文可以选择使用或不使用。

但更重要的是，因为Update是Get后跟函数再跟Set，所以在处理列表方面，它不如您的代码高效：镜头对于列表中的更新首先获取列表中的第n个元素，这是一个O(n)操作。

总结一下：

优点：

• 非常简洁。
• 支持pointfree风格。
• 涉及镜头的代码通常不关心源类型表示（它可以是类、记录、单个案例的DU、字典，不重要）。

缺点：

• 在某些情况下可能效率低下。
• 由于缺少宏，需要一些样板文件。

感谢这个例子，结果我将会修正FSharpx镜头的当前设计并查看是否可以进行优化。

我已经提交了这段代码到FSharpx存储库：https://github.com/fsharp/fsharpx/commit/136c763e3529abbf91ad52b8127ce11cbb3dff28

- Mauricio Scheffer

---

太棒了，非常感谢你在我这个愚蠢的小例子中投入了这么多的心血，并不仅回答了问题，还提供了许多额外的思考内容。非常感激。（我不想取消已经接受的答案，所以希望你能接受简单的点赞）。 - bknotic

Answer 2

我之前问了一个类似的问题，但是关于Haskell：有没有一种Haskell惯用法可以更新嵌套的数据结构？

优秀的回答提到了一种称为函数式镜头的概念。

---

不幸的是，我不知道F#的包是什么，或者它是否存在。

更新：两位知识渊博的F#开发者在评论中留下了有关此问题的有用链接，因此我将在此处发布它们：

• @TomasPetricek建议使用FSharpX和这个网站来描述它

• @RyanRiley给出了该软件包的链接

这两个家伙花时间阅读我的答案，发表评论并加以改进真是太棒了，因为他们都是FSharpX的开发人员！

---

更多无关紧要的信息：我被Clojure的assoc-in和update-in函数所激励，这表明在函数式语言中它是可能的！ 当然，Clojure的动态类型使得它比Haskell/F#更简单。 Haskell的解决方案涉及模板化，我相信。

- Matt Fenwick

---

在FSharpX包中，有一种针对F#的镜头实现。请查看Mauricio Scheffer的描述： http://bugsquash.blogspot.com/2011/11/lenses-in-f.html 。这似乎是一个有趣的选择，但它仍然是一种实验性设计 - 它并不是F＃中真正标准的模式（至少目前还不是）。 - Tomas Petricek

感谢您指出您的问题 - 那里有很多有趣的链接！ - bknotic

@TomasPetricek：谢谢，我会看一下的。 - bknotic

请留意 FSharpx，即将发布 NuGet 版本，其中包含 Lenses。如果你想要获取 Lenses，也可以现在拉取源代码。对应的链接分别为：FSharpx 和 source。 - user29439

Answer 3

我大约一年前发布了一个关于Scala的类似问题。答案提到了三个概念作为解决这个问题的方法：Zippers，树重写和Lenses。

- missingfaktor

---

感谢您指出了您的问题。现在，这个线程积累了相当多关于解决问题的知识！ - bknotic

Answer 4

我不知道为什么你想在这里使用类。我认为，如果您使用记录来保存数据并使其最小化，您可以利用模式匹配的强大功能：

// 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

那么，你可以看到操作这些嵌套的数据结构会更容易。然而，上述函数仍然存在冗余。如果你使用记录（records），可以使用非常自然的镜头（lenses）进行重构。请查看Mauricio Scheffer撰写的深入文章，它与此公式非常接近。

- pad

---

@bknotic 记录类型可以像类一样拥有成员。不同之处在于，它们只能有一个公共构造函数，该构造函数分配给所有字段，这些字段必须是公共的。 - Ramon Snir

@Ramon Snir: 那么您提议如何避免类型的辅助函数泄露呢？将它们设置为私有成员？将它们放在私有模块中？还是使用 .fsi 文件？我很好奇，不过也许这个问题值得一整个新问题的讨论。 - bknotic

@bknotic：我更喜欢使用私有模块，因为使用.fsi可以帮助限制程序集级别的访问控制。 - pad

填充：是的，我只是不喜欢这样做（并不意味着它是不可能或非法的）。我更喜欢使用.fsi文件。@kbnotic所有解决方案本质上都是相同的。如果只有几个，请选择私有成员。如果有很多，请选择私有模块。如果您不介意有两个文件（.fs和.fsi），请选择.fsi。 - Ramon Snir

@pad，Ramon Snir：谢谢大家，我一定会再次查看组件设计并尝试您的建议。 - bknotic

Answer 5

我已经通过反射在C#中实现了一个镜头库。该库的核心是这个函数。

/// <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就可以让它工作了。我不必提供getter和setter。

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 生成来提高性能。

- bradgonesurfing