Updating nested immutable data structures

Question

I want to update a nested, immutable data structure (I attached a small example of a hypothetical game.) And I wonder whether this can be done a little more elegantly.

Every time something inside the dungeon changes we need a new dungeon. So, I gave it a general update member. The best way to use this, that I could come up with for the general case, is to specify the processing functions for each nesting and than pass the combined function to the update member.

Then, for really common cases (like applying a map to all the monsters on a specific level), I provide extra members (Dungeon.MapMonstersOnLevel).

The whole thing works, I would just like to know, if anyone can think of better ways of doing it.

Thanks!

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

Here's the same code using lenses as currently defined in FSharpx. As other answers note, it's convenient to use records here; they give you structural equality for free among other things. I also attach the corresponding lenses for the properties as static members; you can also define them in a module or as loose functions. I prefer static members here, for practical purposes it's just like a module.

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

I also define print as a static member; again it's like a function in a module, and it's more composable than an instance method (though I won't compose it here).

Now to generate the sample data. I think { Monster.Awake = true } is more desciptive than new Monster(true). If you wanted to use classes I'd name the parameter explicitly, e.g. 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 

Now comes the fun part: composing lenses to update the monsters for all rooms for a particular level in a 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 

For the second dungeon I also use lenses but without lens composition. It's sort of a DSL defined by small composed functions (some of the functions are from lenses). Maybe there are lenses to express this more concisely, but I haven't figured it out.

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

I overused lenses and pointfree a bit here, partially on purpose, just to show what it could look like. Some won't like it, claiming it's not idiomatic or clear. Maybe so, but it's another tool that you can choose to use or not, depending on your context.

But more importantly, because Update is a Get followed by a function followed by a Set, this isn't as efficient as your code when it comes to processing lists: an Update in Lens.forList first gets the nth element in the list, which is an O(n) operation.

To summarize:

Pros:

• Very concise.
• Enables pointfree style.
• Code involving lenses is generally oblivious of the source type representation (it can be a class, a record, a single-case DU, a dictionary, it doesn't matter).

Cons:

• May be inefficient for some cases in current implementation.
• Due to lack of macros, requires some boilerplate.

Thanks for this example, as a result I'll be revising the current design of lenses in FSharpx and see if it can be optimized.

I committed this code to the FSharpx repository: https://github.com/fsharp/fsharpx/commit/136c763e3529abbf91ad52b8127ce11cbb3dff28

Answer 2

I asked a similar question, but about haskell: Is there a Haskell idiom for updating a nested data structure?

The excellent answers mentioned a concept known as functional lenses.

---

Unfortunately, I don't know what the package is, or if it even exists, for F#.

Update: two knowledgeable F#-ists (F#-ers? F#as?) left useful links about this in comments, so I'll post them here:

• @TomasPetricek suggested FSharpX and this website describing it

• @RyanRiley gave the link for the package

It's awesome that these two guys took the time to read my answer, comment and improve it, as they're both developers of FSharpX!

---

More extraneous information: I was motivated to figure out how to do this by Clojure's assoc-in and update-in functions, which proved to me that it is possible in functional languages! Of course, Clojure's dynamic typing makes it simpler than in Haskell/F#. Haskell's solution involves templating, I believe.