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

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()

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

Answer 2

我问了一个类似的问题,但是关于haskell: 是否有用于更新嵌套数据结构的Haskell习语？

优秀的答案提到了一个称为功能性镜片的概念.

不幸的是,对于F#,我不知道包是什么,或者它是否存在.

更新:两个知识渊博的F#-ists(F#-ers？F#as？)在评论中留下了有用的链接,所以我会在这里发布:

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

• @RyanRiley给出了包的链接

这两个人花时间阅读我的答案,评论并改进它,真是太棒了,因为他们都是开发者FSharpX!

更多无关的信息:我有动力通过Clojure assoc-in和update-in函数弄清楚如何做到这一点,这证明了它在函数式语言中是可能的!当然,Clojure的动态类型使其比Haskell/F#更简单.我相信,Haskell的解决方案涉及模板化.

Answer 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

然后你可以看到操纵这些嵌套数据结构要容易得多.但是,上述功能仍然具有冗余.如果您使用非常自然的记录镜片,您可以重构更多.查看Mauricio Scheffer撰写的富有洞察力的文章,这篇文章非常接近这个公式.

Answer 4

大约一年前，我发布了一个关于Scala的类似问题。答案提到了三个概念来解决此问题：拉链，树重写和镜头。