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

Question

我想更新一个嵌套的、不可变的数据结构(我附上了一个假设游戏的小例子。)我想知道这是否可以更优雅地完成。

每次地牢中的某些东西发生变化时，我们都需要一个新的地牢。所以，我给了它一个普通的更新成员。对于一般情况，我可以提出的最佳使用方法是为每个嵌套指定处理函数，然后将组合函数传递给更新成员。

然后，对于非常常见的情况(例如将 map 应用于特定级别的所有怪物)，我提供了额外的成员( 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()

Answer 1

这是使用当前在 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 }比 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，所以在处理列表时，这不如您的代码高效:Lens.forList 中的 Update 首先获取列表中的第 n 个元素，这是一个 O(n) 操作。

总结一下:

优点:

非常简洁。

启用无点样式。

涉及镜头的代码通常会忽略源类型表示(它可以是类、记录、单例 DU、字典，没关系)。

缺点:

在当前实现中的某些情况下可能效率低下。

由于缺少宏，需要一些样板文件。

感谢这个例子，因此我将修改 FSharpx 中当前的镜头设计，看看是否可以对其进行优化。

我将此代码提交到 FSharpx 存储库: https://github.com/fsharp/fsharpx/commit/136c763e3529abbf91ad52b8127ce11cbb3dff28