More Intuition on Optics
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:
- minimise the amount of necessary work in witnessing the abstraction
- 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 partsPrism[X, Y]
— a X has a Y or some other partsTraversal[X, Y]
— a X has some number of Y values and/or some other partsIso[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
toY
ifX
has aY
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
toY
ifX
has some number ofY
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.