Handling nested records of lists in f#

Question

I am currently having some trouble elegantly handling nested record lists.

lets say we have the types:

type BoxEntry = {
     flag : bool
}

type Box = {
     entries : BoxEntry list
}

type Entry = {
     boxes : Box list
}

type Model = {
    recEntries : Entry list
}

Now lets say I want to set a specific boxentry bool I have the list indexes of Entry, Box and BoxEntry however I have only found this approach to work for me:

let handleUnsetEntry (model : Model) (idxs : string* int * int) =
    let(sendId, bi, ej) = idxs

    let nEntry =
        model.entries
            |> List.map(fun x ->
                if x.sendId = sendId then
                   {x with boxes =
                            x.boxes |> List.mapi (fun i y ->
                                if i = bi then
                                    {y with boxEntry =
                                                y.boxEntry |> List.mapi (fun j z ->
                                                                if j = ej then
                                                                    z.SetFlag
                                                                else
                                                                    z)}
                                else
                                    y)}
                else
                    x)


    {model with entries = nEntry}, Cmd.none

This is obviously a really silly solution both efficiency-wise as well as readability-wise. Is there another approach to this which is more elegant I feel like there surely must be but I am not getting it.

Any help would be appreciated.

Answer 1

In FP there's a pattern called Lens or Prism. It's kind of composable functional attributes to simplify handling of nested immutable structures.

Lenses/Prisms allows you to zoom in on a nested attribute and get/set it while preserving immutability (set returns a new object).

Lenses/Prisms doesn't really answer what to do IIRC with structures that contains lists but if we ignore that and "hack something" we could end up with something like this:

type Prism<'O, 'I> = P of ('O -> 'I option)*('O -> 'I -> 'O)

That is, a prism consists of two functions; a getter and a setter. The getter given an outer value returns the inner value if it exists. The setter creates a new outer value given a new inner value.

This allows us too define the commonly used fstL and sndL prisms that allows zooming on the first respectively the second part of a pair.

let fstL = 
  let g o         = o |> fst |> Some
  let s (_, s) i  = (i, s)
  P (g, s)

let sndL = 
  let g o         = o |> snd |> Some
  let s (f, _) i  = (f, i)
  P (g, s)

We also define a way to combine two prisms

// Combines two prisms into one
let combineL (P (lg, ls)) (P (rg, rs)) =
  let g o   = 
    match lg o with 
    | None    -> None
    | Some io -> rg io
  let s o i = 
    match lg o with
    | None    -> o
    | Some io -> ls o (rs io i)
  P (g, s)
let (>->) l r = combine l r

Using this we can define a prism that allows zooming into a rather complex structure:

let l = sndL >-> sndL >-> fstL
let o = (1, (2, (3, 4)))
get l o |> printfn "%A"  //Prints 3
let o = set l o 33
get l o |> printfn "%A"  //Prints 33

Given the Model given by OP we extend it with Prisms static attributes

type BoxEntry = 
  {
    flag : bool
  }
  member x.SetFlag = {x with flag = true}

  // Prisms requires some boiler plate code, this could be generated
  static member flagL = 
    let g (o : BoxEntry)    = Some o.flag
    let s (o : BoxEntry) i  = { o with flag = i }
    P (g, s)

Putting it all together we can rewrite the handle function to something like this:

let handleUnsetEntry (model : Model) (idxs : string* int * int) =
  let (sendId, bi, ej) = idxs

  // Builds a Prism to the nested flag
  let nestedFlagL = 
    Model.entriesL 
    >-> Prism.listElementL   (fun _ (e : Entry) -> e.sendId) sendId
    >-> Entry.boxesL
    >-> Prism.listElementAtL bi
    >-> Box.boxEntryL
    >-> Prism.listElementAtL ej
    >-> BoxEntry.flagL

  Prism.set nestedFlagL model true

Hope this gave OP some ideas on how one can handle nested immutable structures.

The full source code:

// A Prism is a composable optionally available property
//  It consist of a getter function that given an outer object returns 
//    the inner object if it's there
//  Also a setter function that allows setting the inner object 
//    (if there's a feasible place)
//  In FP there are patterns called Lens and Prisms, this is kind of a bastard Prism
type Prism<'O, 'I> = P of ('O -> 'I option)*('O -> 'I -> 'O)

module Prism =
  let get (P (g, _)) o    = g o
  let set (P (_, s)) o i  = s o i

  let fstL = 
    let g o         = o |> fst |> Some
    let s (_, s) i  = (i, s)
    P (g, s)

  let sndL = 
    let g o         = o |> snd |> Some
    let s (f, _) i  = (f, i)
    P (g, s)

  // Combines two prisms into one
  let combineL (P (lg, ls)) (P (rg, rs)) =
    let g o   = 
      match lg o with 
      | None    -> None
      | Some io -> rg io
    let s o i = 
      match lg o with
      | None    -> o
      | Some io -> ls o (rs io i)
    P (g, s)

  // Creates a Prism for accessing a listElement
  let listElementL sel k =
    let g o   =
      o
      |> List.mapi    (fun i v -> (sel i v), v) 
      |> List.tryPick (fun (kk, vv) -> if k = kk then Some vv else None)
    let s o i = 
      o
      |> List.mapi    (fun i v -> (sel i v), v) 
      |> List.map     (fun (kk, vv) -> if k = kk then i else vv)
    P (g, s)

  let listElementAtL i =
    listElementL (fun j _ -> j) i

type Prism<'O, 'I> with
  static member (>->) (l, r) = Prism.combineL l r

// Modified model to match the code in OPs post

type BoxEntry = 
  {
    flag : bool
  }
  member x.SetFlag = {x with flag = true}

  // Prisms requires some boiler plate code, this could be generated
  static member flagL = 
    let g (o : BoxEntry)    = Some o.flag
    let s (o : BoxEntry) i  = { o with flag = i }
    P (g, s)

type Box = 
  {
    boxEntry : BoxEntry list
  }

  static member boxEntryL = 
    let g (o : Box)    = Some o.boxEntry
    let s (o : Box) i  = { o with boxEntry = i }
    P (g, s)

type Entry = 
  {
    sendId : string
    boxes : Box list
  }

  static member sendIdL = 
    let g (o : Entry)    = Some o.sendId
    let s (o : Entry) i  = { o with sendId = i }
    P (g, s)

  static member boxesL = 
    let g (o : Entry)    = Some o.boxes
    let s (o : Entry) i  = { o with boxes = i }
    P (g, s)

type Model = 
  {
    entries : Entry list
  }

  static member entriesL = 
    let g (o : Model)    = Some o.entries
    let s (o : Model) i  = { o with entries = i }
    P (g, s)

let handleUnsetEntry (model : Model) (idxs : string* int * int) =
  let (sendId, bi, ej) = idxs

  // Builds a Prism to the nested flag
  let nestedFlagL = 
    Model.entriesL 
    >-> Prism.listElementL   (fun _ (e : Entry) -> e.sendId) sendId
    >-> Entry.boxesL
    >-> Prism.listElementAtL bi
    >-> Box.boxEntryL
    >-> Prism.listElementAtL ej
    >-> BoxEntry.flagL

  Prism.set nestedFlagL model true

[<EntryPoint>]
let main argv = 
  let model : Model =
    {
      entries = 
        [
          {
            sendId  = "123"
            boxes   = 
              [
                {
                  boxEntry = 
                    [
                      {
                        flag = false
                      }
                      {
                        flag = false
                      }
                    ]
                }
              ]
          }
        ]
    }

  printfn "Before change"  
  printfn "%A" model

  let model = handleUnsetEntry model ("123", 0, 0)

  printfn "After 1st change"  
  printfn "%A" model

  let model = handleUnsetEntry model ("123", 0, 1)

  printfn "After 2nd change"  
  printfn "%A" model

  let model = handleUnsetEntry model ("Hello?", 0, 1)

  printfn "After missed change"  
  printfn "%A" model

  0