← All articles

More Intuition on Optics

Tony Morris, Wed Aug 12 2020

In the previous article on Optics, we looked at the two fundamental principles of abstraction, lenses, prisms and traversals. Let's summarise these.

The goals of an abstraction are to:

  1. minimise the amount of necessary work in witnessing the abstraction
  2. maximise the amount of free work that comes about from having witnessed that abstraction

We can see a trade-off in abstractions that subclass one another. For example, Applicative is an abstraction to which Monad is a subclass. The Applicative abstraction has some minimal constraints that are necessary to witness and as a consequence, we derive some amount of free work. The Monad abstraction requires strictly more necessary work to witness, and as a consequence, strictly more free work is derived as a result. These two abstractions both serve a purpose to a user who is given a choice of where to trade-off.

A summary intuition for the optics we have seen so far:

  • Lens[X, Y] — a X has a Y and some other parts
  • Prism[X, Y] — a X has a Y or some other parts
  • Traversal[X, Y] — a X has some number of Y values and/or some other parts
  • Iso[X, Y] — a X has a Y and no other parts

These intuitions are somewhat loose and serve as an indication for which optic relationship we might be observing. They are not strict definitions by any stretch. We observed that the composition of a Lens and Prism results in a Traversal. The Traversal abstraction requires strictly weaker constraints than both Lens and Prism and as a consequence, we derive strictly less free work.

We also observed that an optic, such as Lens, does not necessarily have to have a relationship between a data type that has a field. For example, we talked about the lens; given a key K, return a Lens[Map[K, V], Option[V]]. This is possible, even though a Map does not have a field of the type Option[V]. Let's write that lens.

def mapLens[K, V](k: K): Lens[Map[K, V], Option[V]] =
  Lens[Map[K, V], Option[V]](_.get(k)) {
    case None => m => m.isDefinedAt(k) match {
      case false => m
      case true => m - k
    }
    case Some(v) => _ + ((k, v))
  }

We'll create some test data by initialising a Map[String, String]:

val states =
  Map(
    ("QLD", "Queensland"),
    ("NSW", "New South Wales"),
    ("VIC", "Victoria"),
    ("SA", "South Australia")
  )

Next, let's start using this lens:

// Some("New South Wales")
val r1: Option[String] =
  mapLens("NSW").get(states)

// states Map without the "NSW" entry
val r2: Map[String, String] =
  mapLens("NSW").set(None)(states)

// states Map with "NSW" set to "New Wales"
val r3: Map[String, String] =
  mapLens("NSW").set(Some("New Wales"))(states)

// states Map unchanged
val r4: Map[String, String] =
  mapLens("ABC").set(None)(states)

// states Map with an additional entry ("ABC", "Alpha Bravo Charlie")
val r5: Map[String, String] =
  mapLens("ABC").set(Some("Alpha Bravo Charlie"))(states)

You'll notice that these lens operations are get and set, but we can also modify a current value, using the existing value:

// states Map with the "NSW" entry reversed "selaW htuoS weN"
val r6 =
  mapLens("NSW").modify(_.map(_.reverse))(states)

// states Map unchanged
val r7 =
  mapLens("ABC").modify(_.map(_.reverse))(states)

The utility of a lens may seem rather uninteresting at this point; after all, we can get, set and modify, but these operations (or free work) are pretty close to the definition of a lens (or the initial work we had to perform in writing the lens).

However, given a lens, there are many other operations that we can also utilise. For example, suppose this data type called State, which models mutation in a pure-functional context:

case class State[A, B](run: A => (A, B)) {
  def map = ...

  def flatMap = ...
}

We are able to construct a State value using a lens:

def passthrough[A, B](f: A => B): Lens[A, B] => State[A, B]

This is an example of a use-case with a practical use that may not be immediately evident. After all, to see its use, you'd have to be familiar with both lenses and the State data structure and its related API. I think this is quite a big ask. Let's leave it to a later post.

However, let's look at another example. Recall prisms?

There is a prism from X to Y if X has a Y or some other parts.

There is a prism from Option[A] to A through the Some constructor. Let us call this prism, some:

def some[A]: Prism[Option[A], A] =
  ...

When we compose a Lens and a Prism, we arrive at a Traversal and indeed, we can compose our mapLens with the some prism. Recall, given a Lens[A, B] and a Prism[B, C], then under composition, we will have a Traversal[A, C].

This will give us operations that work directly on the value associated (V) with the given key (K), rather than going through Option:

// given a Lens[Map[K, V], Option[V]]
// and a Prism[Option[V], V]
// then under composition
// we have a Traversal[Map[K, V], V]
def mapLensSome[K, V](k: K): Traversal[Map[K, V], V] =
  mapLens(k) compose some

We can then use this Traversal directly on the value associated with a given key.

// Some("New South Wales")
val r8: Option[String] =
  mapLensSome("NSW").headOption(states)

// None
val r9: Option[String] =
  mapLensSome("ABC").headOption(states)

// states Map with "NSW" set to "New Wales"
val r10: Map[String, String] =
  mapLensSome("NSW").set("New Wales")(states)

// states Map with the "NSW" entry reversed "selaW htuoS weN"
val r11 =
  mapLensSome("NSW").modify(_.reverse)(states)

// states Map unchanged
val r12 =
  mapLensSome("ABC").modify((_: String).reverse)(states)

More on Traversals

We will go back to using our vehicle registration database example from the previous post:

case class Person(name: String, age: Int)

case class VehicleRegistration(num: String, owner: Person)

case class Vehicle(make: String, reg: VehicleRegistration)

Recall:

There is a traversal from X to Y if X has some number of Y values and/or some other parts.

It could be said that there exists a traversal from anything to anything else. After all, it is true that Person has some number of Map[Vehicle, String] values — namely 0 of them — and so there can be a Traversal[Person, Map[Vehicle, String]]. This would be correct. It is an empty traversal. It "touches" all of the Map[Vehicle, String] values within a Person, of which there are none. Its use would leave the Person value unmodified and if we used headOption on the traversal, we would always get None. But what do we mean for a traversal to "touch" a value? Let's look at the definition of a Traversal:

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

The single abstract function for a traversal here is modify and it is all other traversal operations that derive from this one (the free work). Observe that it is traversing through the object A and modifying the B values with the given function. Not only that, it runs some Applicative effect on each modification and Applicative effects can be chained together. It is this "chaining together" effect that gives us the intuition, "some number of parts (whose type we have called B)".

We already know that a Person has a lens to a String; specifically, the name field. However, suppose at some later date, we decide to change the object to have both a firstName and a surname:

case class Person(firstName: String, surname: String, age: Int)

We could now implement two different lenses; one for firstName and one for surname. If we had a use-case to let's say, turn all the firstName characters to upper-case, we could use this lens. However, what if we had the use-case of doing this for both firstName and surname? That is, we want to operate on both String values all at once. This is where a traversal will help us. Let's write the traversal from Person to String and in doing so, we will "touch" both of these fields:

def names: Traversal[Person, String] =
  new Traversal[Person, String] {
    def modify[F[_]](f: String => F[String])
                    (implicit A: Applicative[F]) =
      p =>
        A.apply2(f(p.firstName), f(p.surname)) {
          case (f, s) => Person(f, s, p.age)
        }
  }

Notice in the implementation of this traversal that we have used the function (f) on both of the name fields and combined those two results using the Applicative. We have then reconstructed the Person using the two values from the effects, while we have left the age field alone — merely copied in back to the new Person. It is the use of the function on both fields that we mean by "touching" those fields. This traversal will operate on both of these String fields because they have both been touched in the traversal.

Let's try it:

// Person(FRED, FLINTSTONE, 33)
val r13: Person =
  names.modify(_.map(_.toUpper))(fred)

// Person(Mary, Mary, 33)
val r14: Person =
  names.set("Mary")(fred)

// List(Fred, Flintstone)
val r15: List[String] =
  names.getAll(fred)

// true
val r16: Boolean =
  names.exist(_.startsWith("F"))(fred)

We can see the results of some of our traversal operations in that the results are working on both firstName and surname. This is a consequence of the implementation of our traversal. However, we are not done.

Recall:

All optics are closed under composition

What does this mean? It means, for example, if we have an optic such as a Traversal[A, B] and a Traversal[B, C], then under composition, we get a Traversal[A, C]. Put this aside. Would you agree that a String has some number of Char and/or some other parts? Let's write the traversal that operates on all of them!

def chars: Traversal[String, Char] =
  new Traversal[String, Char] {
    def modify[F[_]](f: Char => F[Char])
                    (implicit A: Applicative[F]) =
      _.toList.traverse(f).map(_.mkString)
  }

This traversal implementation "touches" every character of a String and so any operation will work on all Char values. We can take our existing names traversal and compose it with our chars traversal. This will give us direct access to every character in both names of a Person:

// names: Traversal[Person, String]
// chars: Traversal[String, Char]
def nameChars: Traversal[Person, Char] =
  names compose chars

Now we can use it:

// Person(FRED, FLINTSTONE, 33)
val r17: Person =
  nameChars.modify(_.toUpper)(fred)

// Person(XXXX, XXXXXXXXXX, 33)
val r18: Person =
  nameChars.set('X')(fred)

// List('F','r','e','d','F','l','i','n','t','s','t','o','n','e')
val r19: List[Char] =
  nameChars.getAll(fred)

// false
val r20: Boolean =
  nameChars.exist(_ == 'x')(fred)

Some interesting observations

Take note of the implementation of the names traversal. The full power of Applicative is required to implement this, since it touches both firstName and surname. Observe, however, that if we chose to only touch one of the names, then we would not require this full power, since we'd only be using the map function. In other words, we could weaken the Applicative to simply Functor if that were our use-case.

Some data types, particularly recursive data types, have a Traversal to values of itself. For example, consider this data type:

case class Tree[A](root: A, children: List[Tree[A]])

We could write a Traversal[Tree[A], Tree[A]] that traverses each immediate child node of a tree. What useful operations might we derive from this traversal?

We will explore these observations and dive further into other things that we can do with optics in the next part.