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 `modify`

ing 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`

.

**Lesson 1:** Lenses: Used to modify nested data structures

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:

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:

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:

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

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

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`

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.

**Lesson 2:** Seemingly distinct functions may share a common abstract representation

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

**Lesson 3:**Use helper functions to convert to whichever representation most suits the code you want to write

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

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:

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:

**Lesson 4:**Your code is often hiding a more general abstraction (with more type parameters)

## 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 `Int`

s together: `_*_`

, would create a function that took two `Option`

s, 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`

.

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 `Branch`

es and `Leaf`

s. 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`

- This results in “mapped” versions of these trees, contained within the
- We call the
`f`

argument to the apply function on the value- This results in a “mapped” value, contained within an
`Applicative`

- This results in a “mapped” value, contained within an
- We use
`fmap3`

, to combine the`Applicative`

s 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 `BinaryTree`

s 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 `Const`

s.

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`

.

`Monoid`

s 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.

`Monoid`

s 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 `Traversal`

s 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.

**Lesson 5:**A Traversal is like a Lens, with many Foci

## 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`

.

`Traversal`

s 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`

.

**Lesson 6:**Well known type hierarchies have more to them than you may think

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.

- If you are looking to use optics in Scala in real world code, I’d
- 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.