Lenses and lists

6 min readJul 11, 2016

How to change the thing amongst the other things in that thing…maybe.

Last time we talked about a very useful device called Lenses, for dealing with change in complex nested value structures, immutably. This time we’ll expand this idea to deal with a few cases that are a bit trickier.

The Problem

Let me tell you a story. We’ll continue with the same program as we used last time. That is, a person type that has some contact details, which in turn contains addresses. Since last time the dev team “discovered” that people had more than just a home and work address, and in fact could have a variety of addresses. Therefore, it makes sense to have a more fluid collection instead.

type Address{
  name: string;
  number: int;
  street: string;
  city: string;
  state: string;
  country: string;
}type ContactDetails {
  numbers: string list;
  addresses: Address list;
}type Person = { 
   name: string; 
   age: int; 
   contact: ContactDetails
}

So now we have a collection of addresses that are named. This seems all very sensible and worked quite well.

Expanding Lenses

Challenge: we need a new lens function that can work with elements of a list

Let’s start with the common requirement to add and remove items from a list. This ends up being fairly straight forward — we just update the container’s lens with a list with an extra / removed element.

let inline (@=) lens v = lens.update (List.append [v])
let inline (-=) lens v = lens.update (Array.filter (fun a -> v <> a))let updatedPerson = person |> (Contact >>| Addresses ) @= anAddress

Getting an element from the list gets a little bit more gnarly. We can create a function that returns the nth element, but the element may not exists if the index is out of bounds. It would be nice to follow the pattern that F# standard libraries give us with functions like tryFind() with an option type; return “None” when out-of-bounds, or “Some X” .

let nth (n:int) : Lens<’a list,’a option> =
 {
   get = fun theList ->
     match n with
     | x when x < 0               -> None
     | x when x >= theList.Length -> None
     | _                          -> Some( theList.[n] )
   set = fun v -> 
      List.mapi (fun i elem -> if i = n then v.Value else elem)
 }

So now we should be able to change the third addresses city as follows

let lens = ( Contact >>| Addresses >>| nth 2 >>| City )
let updated = myPerson = lens.set "Christcurch"

Well, close but not quite. the problem is that nth returns an option. What if the option is “None”? Even if it is “Some X”, the next operation doesn’t take an option, so we would need to de-reference the value to pass it along the chain.

Optional composition

Challenge: we need another combinator that stops at a None, or continues down that chain with the “Some” value.

We’re going to create a new operator that can combine optional and non-optional lenses. I’m made up the combination >>|| for this.

let inline (>>||) 
  (l1: Lens<'a,'b option>) 
  (l2: Lens<'b,'c >) 
  : Lens<'a, 'c option> =
   {
     get = fun (a:'a) ->
        let b = l1.get a
        match b with
        | None -> None
        | Some bVal -> Some( l2.get bVal )
...

As seems to always be the case the get operation is fairly straight forward. We take a lens that returns and option and one that accepts the same type (but not an option). To get the value we either return “None” to stop the chain, or wrap a “Some” around the second lens’s value.


...
     set = fun (c:'c option) (a:'a) ->
        let b = l1.get a
        match b,c with
        | Some bVal, Some cVal ->
           let optionBridge = 
             fun (x: 'b option) -> l2.set cVal (x.Value) |> Some
           l1.update optionBridge a
        |_,_ -> a
  }

To set a value down the chain is a bit trickier because we are in effect going backwards up the chain. Therefore both the optional container might be “None”, and the inner value could also be “None”. We only progress with the change if both sides have values, otherwise no change is made at all. As you may see the little option bridge function sets the inner value, and then wraps in a “Some” to pass it back to the optional container. We use this as the function for the update function on the containing lens.

Now we can get to that nth city.

let lens = ( Contact >>| Addresses >>| nth 2 >>|| City )
let updated = myPerson = lens.set "Christcurch"

The person may or may not have been updated, depending on whether we have 3 addresses, or not. We may want to treat this as a failure, but we’re not going to get into that at this point.

This worked quite well (in dev) until someone pointed out that we have named addresses, and unless you have a generous UI the user may not know the index.

Collection Searching Lenses

Challenge: we want to access a collection item by name

Again we need an optional lens, but now we need one that filters based on a property of the element itself — that sounds just like a tryFind() function!

let inline where (pred: 'a -> bool ) : Lens< 'a list,'a option> = 
    {
      get = fun theList -> theList |> List.tryFind (pred)
      set = fun v ->
          List.map (fun elem -> if pred elem then v.Value else elem)
    }

So, now we can get the “work” address and change the city based on a predicate we pass in to identify the correct address.

let compoundLens = 
    Contact 
    >>|  Addresses 
    >>|  where (fun x -> x.name = "work")
    >>|| city

This is really flexible and can work on any type and any condition, which is really great for impromptu searches.

However, we found that we repeated this pattern many times so that we had a lot of named types. We ended up typing this “where” clause a lot, and would like to find a shortcut.

Duck typed lenses

This is an “extra for experts” section for the especially lazy. F# has a great system for loosening the type constraints a little by using duck typing.

We can create a function that doesn’t care what the type is, as long as it has a name value to compare against.

let inline isNamed <^a when ^a:(member name:string)> (nm:string) a = 
      (^a:(member name: string) a) = nm

Then we can wrap a lens around this function

let inline byName<^a when ^a:(member name:string)> (nm:string)
                :Lens<^a list,^a option> = 
 {
   get = fun theList -> theList |> List.tryFind (isNamed nm)
   set = fun v -> 
    List.map (fun elem -> if (isNamed nm) elem then v.Value else elem)
 }

Finally, we can create our more efficient, possibly more readable, compound lens and change the city value.

let compoundLens = Contact >>| Addresses >>| byName "work" >>|| City
let updated = myPerson |> compoundLens.set "Christchurch"

Continuing on

This is article #4 in this series, and completes the topic of using lenses. Next time we delve into the arcane art of using types at compile-time, based on external data sources: type providers.

Records: Just like the that one, only different.
The OO way: implementing property setters in F# to “cheat” by creating a C#-style mutable object.
Lenses: changing the thing inside the thing inside the other thing.
Lenses and lists: appending, deleting, and replacing elements in a collection in an object
Two-way Type Providers: reflecting changing external data
Some common things that usually rely on mutation: like sorting…