Lessons Learned Building a Van Laarhoven Lens Library

This blog post is a write-up of a talk that I gave at London Scala User Group in November of 2019. I’d like to take this space to thank London Scala for the opportunity to speak.

In writing this post, I’m assuming the audience has a strong understanding of Scala, and Functional Programming.

What are Lenses

The original motivation for lenses comes from wanting a better syntax for modifying nested records

Consider for example the following case classes.

case class Person(name: String, address: Address)
case class Address(
    houseName: String, 
    streetName: String)

val jane = Person("Jane",
    Address("22B", "Baker Street")
  )

We have a Record containing data about a Person, this includes a Record representing an Address, containing a streetName, that has a type String.

A couple of the ways that we may want to use these records are:

• Getting: We may want to fetch the StreetName for a Person
• Setting: We may want to update the Person with a new StreetName

// Getting
val streetName = jane.address.streetName

//Setting
val janeUpdated = jane.copy(
  address = jane.address.copy(
    streetName = "Sesame Street"
  )
)

This being Scala, we’re not updating our Person in place, we’re creating a new record, that refers to an updated Person.

In my opinion, while the “Getting” example looks great, the “Setting” example leaves a lot to be desired. The copy method that Scala uses to update case classes is really useful, but chaining multiple copy calls together to modify nested data structures can be unwieldy.

It would be great if we had some kind of value representing the relationship between a Person and their Address and an Address and it’s StreetName. It would also be great if we could compose these values together, making a new value representing the relationship between a Person and their StreetName, cutting out the middle level of indirection. We should be able to use such a value to “Get” or “Set” a Person’s StreetName directly, as well as modifying the StreetName with a function.

val personAddressLens = ???
val addressStreetNameLens = ???

// Composition
val personStreetNameLens = Lens.compose(
 personAddressLens,
 addressStreetNameLens)
// Getting
personStreetNameLens.get(jane)

// Setting
personStreetNameLens.set(jane, "Sesame Street")

// Modifying
personStreetNameLens.modify(_.toLowerCase)(jane)

This type of value is called a Lens.

Lets talk about how we might define a Lens. We’ve mentioned that we want to use it for “Getting” and “Setting”, so the Lens interface might look like the following:

trait Lens[S, A] {
 def get(s: S): A
 def set(s: S, a: A): S
}

We’re using two type parameters to define this interface: S, the type of the top level record, and A, the type of the field being focussed on. In our earlier example, Person would have been S and StreetName would have been A, such that personStreetNameLens would have had the type Lens[Person, StreetName].

Earlier, we mentioned that rather than “Getting” or “Setting”, we might want to “Modify” the focus with a function, so lets also add that to the interface:

trait Lens[S, A] {
 def get(s: S): A
 def set(s: S, a: A): S

 def modify(f: A => A)(s: S): S
}

Some of the time, we may want to modify a record using something other than a regular function, such as a partial function, or possibly an asynchronous function. To support this, we may want methods that look like this:

trait Lens[S, A] {
 def get(s: S): A
 def set(s: S, a: A): S

 def modify(f: A => A)(s: S): S

 def modifyMaybe(f: A => Option[A])(s: S): Option[S]
 def modifyFuture(f: A => Future[A])(s: S): Future[S]
}

A Note on Functors

Let’s briefly talk about Functors. If you already know what Functors are, you can probably skip the next few paragraphs. If you don’t, then you might be better off reading the cats documentation, rather than letting me confuse you, but here goes:

Functor is a kind of typeclass. There are Functor instances for any type that can be mapped over; for example Option is a functor.

A definition of Functor may look like the following:

trait Functor[F[_]]{
  def fmap[A, B](f: A => B)(a: F[A]): F[B]
}

We could use a Functor that had been defined in this way to map over an Option, as follows:

val f = implicitly[Functor[Option]]
f.fmap((_: Int).toString)(Some(1)) == Some("1")

This is really just an elaborate way to write the following:

Some(1).map(_.toString) == Some("1")

And it’s typical to define some implicits to provide a nicer syntax for working with Functors.

Returning to our Lens interface. Having introduced Functors, we’re able to get rid of our “Partial” and “Asynchronous” modification methods, and replace them with a single method, that works on any Functor:

trait Lens[S, A] {
 def get(s: S): A
 def set(s: S, a: A): S

 def modify(f: A => A)(s: S): S

 def modifyF[F[_]: Functor](f: A => F[A])(s: S): F[S]
}

The Identity Functor

Let’s introduce a specific Functor instance here, called Identity. At first glance, this may seem so simple as to be useless, but later we’ll see that we can do some cool things with it.

Identity is a Functor that simply wraps a single value. Mapping over the Functor modifies the value.

case class Identity[A](value: A)
implicit val identityFunctor: Functor[Identity] = new Functor[Identity] {
  override def fmap[A, B](f: A => B)(fa: Identity[A]): Identity[B] =    
    Identity(f(fa.value))
}
identityFunctor.fmap((_:Int)*2)(Identity(1)) == Identity(2)

The neat thing about the Identity functor, is that we can use it to convert between functions that work on Functors, and functions that work on values.

In the context of Lenses, we can use it to write modify in terms of modifyF.

trait Lens[S, A] {
 def get(s: S): A 

 def set(s: S, a: A): S = modify(_ => a)(s)

 def modify(f: A => A)(s: S): S = 
  modifyF(a => Identity(f(a))).apply(s).value

 def modifyF[F[_]: Functor](f: A => F[A])(s: S): F[S]
}

Writing modify also gives us set for free, because setting a value is the same as modifying a value with a constant function.

The Const Functor

I’m going to introduce a second functor now. If anything, this may seem even more useless than the Identity functor mentioned above.

The Const Functor takes two type parameters, A and B but only B changes when it’s mapped over. An instance of the Const functor stores a value of type A, and this doesn’t get modified when it’s mapped over.

Mapping a Const Functor doesn’t change the underlying value.

case class Const[A, B](value: A)
implicit def constFunctor[C] = new Functor[({type λ[α] = Const[C, α]})#λ] {
  override def fmap[A, B](f :A => B)(a :Const[C, A]): Const[C, B] = 
    Const[C, B](a.value)
}
constFunctor.fmap((x: Int) => x*2)(Const(1)) == Const(1)
constFunctor.fmap((x: Int) => x.toString)(Const(1)) == (Const(1): Const[Int, String])

The Const functor is useful, because if we create an instance of the Const functor with a particular value, and then pass that instance into functions that are written in terms of the functor interface. These functions won’t be able to change the underlying value, so it will get passed out unmodified.

We can take advantage of this to use the Const functor to write our set method, in terms of modifyF

def get(s: S): A = modifyF(Const[A, A](_)).apply(s).value

The lens can put values into the functor, but it doesn’t know how to modify them. The only way the Lens has of creating a functor is by passing in the Focus.

We’ve now demonstrated that we’re able to write our three initial methods, get, set, and modify in terms of the single method modifyF.

modifyF is the only method that we need to define in order to create a new Lens, and a Lens is in some way equivalent to a function with the same type signature as modifyF.

Scala has some syntactic sugar for types that are equivalent to a function. If we re-name modifyF as apply, we’re able to call a lens as if it were a function directly.

Ultimately, our Lens interface looks like this:

trait Lens[S, A] {
 def get(s: S): A = 
   apply(Const[A, A](_)).apply(s).value

 def set(s: S, a: A): S = modify(_ => a)(s)

 def modify(f: A => A)(s: S): S = 
  apply(a => Identity(f(a))).apply(s).value

 def apply[F[_]: Functor](f: A => F[A])(s: S): F[S]
}

Earlier, we mentioned wanting to compose a lens from Person to Address and a lens from Address to StreetName, Another nice thing about our apply/modifyF method, is that it takes an argument of type A => F[A], and returns a result S => F[S].

Because of the self similarity between these types, it’s possible to use the result of apply on one lens as the argument to another. Doing this, composes the lenses together; lens composition is function composition.

object Lens {
  def compose[S1, S2, A](l1: Lens[S1, S2], l2: Lens[S2, A]) = 
    new Lens[S1, A]{
     override def apply[F[_] : Functor](f: A => F[A]): S1 => F[S2] = 
       l1(l2(f))
   }
}

There’s a lot of boilerplate there, but the thing to pay attention to is that the definition of apply on the resulting lens is simply the apply functions from the two lenses composed together.

When composing two lenses together, it’s convenient that we can define a Lens in terms of just an apply function.

That said, it would be really inconvenient if, whenever we wanted to create a new lens, we had to write it in terms of a function between functions onto Functors. There’s a reason that’s a mouthful.

Instead, it’s much more convenient to write a helper method to take advantage of the equivalence between get+set and modifyF/apply in the opposite direction.

object Lens {
 def lens[S, A](getter: S => A, setter: S => A => S): Lens[S, A] = 
  new Lens[S, A] {
   override def modifyF[F[_] : Functor](f: A => F[A]): S => F[S] = { s =>
	implicitly[Functor[F]].fmap[A, S](setter(s))(f(getter(s)))
   }
  }
}

This makes it much easier to write concrete Lenses:

val personAddressLens = Lens.lens[Person, Address](
  _.address, 
  p => a => p.copy(address = a)
)
val addressStreetLens = Lens.lens[Address, String](
  _.streetName,
   a => s => a.copy(streetName = s)
)

Polymorphism

So far, we’ve talked about using lenses to modify Records with concrete types.

That said, it’s not unreasonable to expect that we should be able to write a Lens that focusses on the first element of a tuple.

And given that an element of a tuple can have any type, it’s not unreasonable to expect that we should be able to modify the type of the focus (thus also changing the type of the resulting tuple).

val a = (1, "world")

val b = Tuples.first.modify((_: Int).toString)(a)

b == ("1", "world")

This is completely possible; it just requires adding some additional type parameters to our Lens interface.

Instead of Lens[S, A] we now have Lens[S, T, A, B]

• S is the type of the record before mapping; (Int, String) in the example above
• T is the type of the record after mapping; (String, String)
• A is the type of the focus before mapping; Int
• B is the type of the focus after mapping; String

Tuples.first has the following type:

  def first[A1, A2, B]: Lens[(A1, B), (A2, B), A1, A2]

And the entire Lens interface looks like the following:

trait Lens[S, T,  A, B] {
 def apply[F[_] : Functor](f: A => F[B]): (S => F[T]) 

 def get(s: S): A = 
  apply(Const[A, B](_)).apply(s).value

 def modify(f: A => B): (S => T) = 
  s => apply(a => Identity(f(a))).apply(s).value

 def set(s: S, b: B): T = 
  modify(_ => b)(s)
}

Because we’ll only rarely be dealing with polymorphic lenses, it’s convenient to define a type alias when working with simple lenses, where mapping doesn’t change the types:

type SimpleLens[S, A] = Lens[S, S, A, A]

The Functor/Applicative/Monad Hierarchy

Lets talk about Functors, Applicatives and Monads. Like the Functor section above, if you’re new to this, it’s covered in more detail in the cats documentation, over in this blog post and also in Learn you a Haskell.

All Applicatives are Functors, and all Monads are Applicatives.

Applicatives add a couple of additional methods to Functor. These methods are pure and fmap2, although there’s an equivalence between ap and another method called ap.

pure takes a plain value, and places it into a “default” Applicative. For example Option is an applicative, and applying pure to a value 1: Int would give you Some(1): Option[Int].

fmap2 takes a binary function; that is, a function between two arguments, and it “lifts” it, onto a function that takes two applicatives. For instance, using the Option fmap2 on a function that multiplied two Ints together: _*_, would create a function that took two Options, multiplying the values if both were present, and returning another option.

optionApplicative.fmap2(_*_)(Some(2), Some(3)) == Some(3)
optionApplicative.fmap2(_*_)(Some(2), None) == None

Several calls to fmap2 can be chained together to make similar “lifting” functions, with more arguments.

def fmap3[A, B, C, Z](f: (A, B, C) => Z)(fa: F[A], fb: F[B], fc: F[C]): F[Z] = {
  val c2z = fmap2((a: A, b: B) => f(a, b, _))(fa, fb)
    ap(c2z)(fc)
}

I’m going to brush over Monads relatively quickly, because despite being generally more well known than Applicatives, in the context of Optics, they don’t come up very often.

Monads add an additional method to Applicatives called join (adding join is equivalent to adding another method, called bind (aka. return, this is often introduced prior to join.)

join takes a Monad that’s nested two layers deep, and flattens it. For example:

optionMonad.join(Some(Some(1)): Option[Option[Int]]) == (Some(1): Option[Int])
optionMonad.join(Some(None): Option[Option[Int]]) == (None: Option[Int])
optionMonad.join(None: Option[Option[Int]]) == (None: Option[Int])

Traversals

Supposing we were to take the characteristic apply function for lenses, that we discussed above. We could take the Functor constraint in the type signature, and replace it with an Applicative constraint.

The broader category of things that are similar to lenses are referred to as optics. The optic produced by replacing the Functor constraint with Applicative is called a Traversal, hopefully the reason for that name will become apparent later.

All Functors are Applicatives, so we’d be strictly reducing the set of arguments that could be passed to the method. Because of this, the Traversal interface is more specialized than Lens. Every Lens can be converted into a Traversal.

trait Traversal[S, T, A, B] {
 def apply[F[_] : Applicative](f: A => F[B]): (S => F[T]) 
}

Before we discus how changing the constraints on apply effect our ability to get/set/modify, lets take a look at a specific concrete implementation of a Traversal.

Binary Trees

A Binary Tree is a type of data structure, that consists of Branches and Leafs. A Branch contains a value, as well as two child trees. A Leaf doesn’t contain anything, the purpose of leaves is to terminate the tree.

We might represent the types in a binary tree in the following way:

sealed trait BinaryTree[A]

case class Branch[A](
    left: BinaryTree[A],
    value: A,
    right: BinaryTree[A]
  ) extends BinaryTree[A]

case class Leaf[A](
    ) extends BinaryTree[A]

We can write a Traversal over a BinaryTree as follows:

def traversal[A, B]: Traversal[BinaryTree[A], BinaryTree[B], A, B] =
  new Traversal[BinaryTree[A], BinaryTree[B], A, B]{
    override def applyTraversal[F[_] : Applicative](f: A => F[B]):
      BinaryTree[A] => F[BinaryTree[B]] = {
        case Leaf() => implicitly[Applicative[F]].pure(Leaf[B])
        case Branch(left, value, right) =>
          implicitly[Applicative[F]].fmap3 {
             (l, v, r) => Branch[B](l, v, r)
          }(
           this.apply(f).apply(left),
           f(value),
           this.apply(f).apply(right)
         )
 }

There are three important parts to pay attention to there.

If we traverse over a Leaf, we use pure to create a new Leaf, within our Applicative.

If we traverse over a Branch,we do a number of things.

• We call the apply function recursively on the two sub trees
  • This results in “mapped” versions of these trees, contained within the Applicative
• We call the f argument to the apply function on the value
  • This results in a “mapped” value, contained within an Applicative
• We use fmap3, to combine the Applicatives with subtrees and the Applicative with the value into a new Applicative with a branch.

By itself, the fact that we can write such a method over BinaryTrees may not seem very interesting, but let’s see what happens when we call this method on specific functors.

Identity; Redux

The Identity Functor that we introduced above is an Applicative:

implicit val identityApplicative: Applicative[Identity] = new Applicative[Identity] {
  override def ap[A, B](ff: Identity[A => B])(fa: Identity[A]): Identity[B] =
    Identity(ff.value(fa.value))

  override def pure[A](a: A): Identity[A] = Identity[A]
}

This means that we can pass in the Identity Functor as an argument to our apply method, similarly to how we did when discussing lenses, in order to modify the targets of a traversal.

val tree = BinaryTree.Branch(
  BinaryTree.Leaf(),
  1,
  BinaryTree.Branch(
    BinaryTree.Leaf(),
    2,
    BinaryTree.Leaf()
  )
)

val t2 = BinaryTree.traversal.modify { 
    i: Int => (i* 2).toString 
  }(tree)

t2 == BinaryTree.Branch(
  BinaryTree.Leaf(),
  "2",
  BinaryTree.Branch(
    BinaryTree.Leaf(),
    "4",
    BinaryTree.Leaf()
  )
)

Const; Redux

Unlike Identity, we are unable to use the Const Functor as an Applicative. To demonstrate this, it’s useful to think about fmap2 and how we’d combine the values in each of the two Consts.

When we were writing Applicative for Identity, the two values in each of the arguments had the same type as the arguments to the function that we were lifting, hence we could combine those values using that function.

In the Const case, it’s possible for the type of the underlying value to differ from the type that we’re mapping with. In that case, we can be stuck with two values, from each Const, with no clear way to combine them.

Monoids

At this point, I’m going to introduce yet another typeclass: The Monoid.

Monoids encompass any type that has a binary operation concat, and a zero element, where these behave according to certain rules.

Those rules are:

• The binary operation must be associative. That is: a concat (b concat c) should be the same as (a concat b) concat c. In other words, in a long chain of those operations, it doesn’t matter where you place the brackets.
• When concat is applied to zero and any other argument, the result must be the other argument. a concat zero == a and zero concat a == a for all possible values of a.

An example of a type where we can define a Monoid is the List. The zero element is the empty list, and concat is list concatenation.

def zero: List[A] = List.empty[A]

def concat( a: List[A], b: List[A]): List[A] = a ++ b

Monoids are relevant, because they can be used to create an Applicative for Const, provided that the value “hidden” in the Const is a Monoid.

Const[A: Monoid, B] is an Applicative.

This is useful, because it means that we can pass a => Const(List(a)) into the Traversals apply function. The result of doing this is like a get function, except that it returns a list of all of the foci of the Traversal.

trait Traversal[S, T, A, B] {
 def apply[F[_] : Applicative](f: A => F[B]): (S => F[T])

 def modify(f: A => B)(fa: S): T =  apply{
     a => Identity(f(a))}.apply(fa).value

 def buildListOf(s: S): List[A] = apply{
   a => Const[List[A], B](List(a))
 }.apply(s).value
}

Applying this to our BinaryTree Traversal

val tree = BinaryTree.Branch(
  BinaryTree.Leaf(),
  1,
  BinaryTree.Branch(
    BinaryTree.Leaf(),
    2,
    BinaryTree.Leaf()
  )
)

BinaryTree.traversal.buildListOf(tree) == List(1, 2)

In general, a Traversal is like a Lens, except instead of having a single focus, it has many foci. Since it has many foci, it isn’t possible to write a get function, but we can get a list.

Because the “characteristic function” for a Traversal has the same “self similar” property that lenses do, we can compose traversals in much the same way as we can compose lenses.

Similarly, because every Lens is a valid Traversal, we can compose lenses and traversals.

Non Empty Trees

Whenever I try to write a BinaryTree implementation from memory, I tend to make the same “mistake”.

This mistake is storing the values in the leaves, as opposed to the branches of the tree.

The resulting data structure has a number of interesting properties. The one that’s is relevant here, is that in any tree, there must be at least one Leaf. Therefore, if we’re storing values in the leaves, we must have at least one value; there’s no such thing as an empty tree.

We can represent a tree where the values are stored in the leaves as follows:

sealed trait NonEmptyTree[A]

case class Branch[A](
    left: NonEmptyTree[A],
    right: NonEmptyTree[A]
  ) extends NonEmptyTree[A]

case class Leaf[A](value: A) 
    extends NonEmptyTree[A]

A Traversal over a NonEmptyTree can be written in a very similar way to a Traversal over a `BinaryTree:

def traversal[A, B]: Traversal[NonEmptyTree[A], NonEmptyTree[B], A, B] 
  = new Traversal[NonEmptyTree[A], NonEmptyTree[B], A, B] {

  override def apply[F[_] : Applicative](f: A => F[B]):
    NonEmptyTree[A] => F[NonEmptyTree[B]] = {

    case Leaf(a) => implicitly[Functor[F]].fmap(Leaf[B](_))(f(a))
    case Branch(left, right) =>
      implicitly[Applicative[F]].fmap2{
        (a, b) => Branch[B](a, b) 
      }(apply(f).apply(left), apply(f).apply(right))
  }
}

There’s one interesting distinction between this Traversal, and the Traversal for a BinaryTree. The Traversal over a BinaryTree used the Applicative.pure method, in order to get a Leaf into the Applicative. The Traversal over a NonEmptyTree didn’t need to, because at no point was there an “empty” value, that needed lifting into the Applicative.

Revisiting the Functor/Applicative/Monad hierarchy, one typeclass, Applicative introduces two functions: pure and fmap2.

It’s possible to add a couple of typeclasses in between Functor and Applicative, one with pure but not fmap2 and one with fmap2 and not pure.

These are commonly known as Pointed (containing pure) and Apply (containing fmap2). Compared to Pointed, Apply is reasonably well known; there is an Apply instance within cats.

A Lens is guaranteed to have exactly one focus. It’s argument contains a Functor.

Traversals swap out the Functor for an Applicative. Unlike a Lens, a Traversal may have zero or many foci.

As alluded to above, an optic with Apply instead of Applicative is guaranteed to have at least one focus. I like to refer to this optic as a NonEmptyTraversal, but there’s an implementation of it in the haskell lens library where it’s called Traversal1.

The fmap2 and ap methods can be used to merge Functors. Since Pointed lacks them, the optic based on pointed cannot have more than one focus. But, because it has a pure function, it can create a Functor from a plain value. The end result of this, is that the optic based on Pointed can have zero or one target, and is called Optional.

By playing around with the Functor heirarchy, and by making some other changes to the interface that aren’t covered in this post, we can come up with a whole range of optics representing relationships between values.

Some (but not all) of there optics are:

I’m going to end, by referencing the webcomic Cartesian Closed Comic.

Since optics represent different relationships between types, such as “is a type of”, or “contains one or more”, they are in many ways, similar to relationships in an old-timey UML class diagram.

But unlike relationships in a UML diagram, optics can be used directly in real (functional code).

References

Source Code:

• Source Code for the optics in this article
• Monocle (Julien Truffaut)
  • If you are looking to use optics in Scala in real world code, I’d highly reconmend using Monocle over my optics code. Monocle has been written with at least some consideration for performance, and also has a stable API, I’m not guaranteeing either.
• Lens (Edward Kmett)
  • This is a Haskell library, it contains a large number of optics, and is relatively intimidating.

Futher Reading:

• CPS based functional references (Twan van Laarhoven)
  • This was the original post that intorduced the “van Laarhoven” representation of Lenses
• Edward Kmett’s Lens Wiki
• Lenses: Compositional Data Access and Manipulation (Simon Peyton Jones)
  • This was a talk, given by Simon Peyton Jones at Haskell Exchange in 2014. SkillsMatter (the organization behind Haskell Exchange) have since gone into Administration, I’m not aware of anywhere that this video can be found online. It gave a fantastic introduction to lenses, and if you’re aware of a link to it, please get in touch.
• The Essence of the Iterator Pattern (Jeremy Gibbons and Bruno C. d. S. Oliveira)
  • This paper first introduced Traversals, it’s full of mathematical notation, is quite intimidating, and covers a lot of interesting ground.