Last week [1], we saw how to use Functor to define a single lift function and how could we write set in terms of modify. Today we will attack the trickiest part of our journey to simplify Lens definition. Do not worry if it does not make sense the first time you read it, I had to watch two or three times Simon Peyton Jones presentation [2] before it starts to make any sense! And fell free to add comments to this blog if you want me to clarify something.
3. Modify
We can see from their type signature that modify and lift are very similar:
def modify(from: S, f: A => A): S def lift[F[_]: Functor](from: S, f: A => F[A]): F[S]
They both take an S and a function from A. The only difference is that lift wrap the return value in a Functor context. If we want to write lift in term of modify, we would need a function to extract an A from F[A] for all Functors and Functor does not define such function (Comonad does). However, if we try to write modify in terms of lift, we only have to pick up one type with a few characteristics:
- it needs to have an instance of Functor
- we need an extract function that pulls out an S out of F[S] (the return type of lift)
- we need a raise function that takes a simple A and raise it to an F[A] (to satisfy f lift function)
If we had such a type F, we could write modify as follow:
def modify(from: S, f: A => A): S = {
type F[X] = ??? // the type we need to define
def raise(a: A): F[A] = ???
def extract(fa: F[A]): A = ???
extract(lift(from, {a: A => raise(f(a)) }))
}
The simplest way to define such a type is to use a case class with a single generic value. We get extract and raise for free from the case class accessor and constructor respectively. So we only have to write an instance of Functor for that dummy type, let's call it Id.
case class Id[A](get: A)
val idFunctor = new Functor[Id] {
def map[A, B](id: Id[A])(f: A => B): Id[B] = Id(f(id.get))
}
def modify(from: S, f: A => A): S = {
def raise(a: A): Id[A] = Id(a)
def extract(id: Id[A]): A = id.get
extract(lift(from, {a: A => raise(f(a)) }))
}
Or simply:
def modify(from: S, f: A => A): S = lift(from, { a:A => Id(f(a)) }).get
Magical isn't it? You write down the type signature of the functions you need and check that everything compile. Then, you only to define or even better find an existing type that respect your contract (you can find Id in Scalaz [3]).
For those of you inclined to early optimisation, you may worry that we are wrapping and unwrapping an object unnecessarily. It turns out that we can define Id with no runtime cost by using the following type synonym:
type Id[A] = A
4. Get
We managed to write set as modify and modify as lift because they are all doing the same thing: updating an A from S and returning the updated S. However, get is not updating anything, it simply reads an A from S. A priori, there is no way to consolidate the updating part of lenses with the reading part. The trick relies on the fact that both modify and lift have access to A when they use their f function. After all, if you want to modify A, you need to access it first!
We are going to use the same methodology than with modify implementation. First, find out what are the desired features of the type F we want to use in lift and then implement a class that satisfy these features:
- F needs to have an instance of Functor
- we need to store an A inside of F[A]
- we need to extract an A out of F[S]
This case is slightly more complicated than modify because the type parameter of F does not match the type of the value we want to store. So we have to construct a type F with two type parameters one for the type of the stored value and a second type to satisfy lift. Since lift expects a type constructor with a single type parameter, we will need to create a type synonym F2 that fix the first type parameter of F.
def get(from: S): A = {
type F[X, Y] = ??? // the type we need to define
def store[B](a: A): F[A, B] = ???
def extract(fa: F[A, _]): A = ???
type F2[B] = F[A,B]
extract(lift[F2](from, {a: A => store[A](f(a)) }))
}
Similarly with Id, we could implement F with a case class, but this time with two accessors:
case class Pair[A, B](first: A, second: B)
def pairFunctor[A] = new Functor[({type F2[B] = Pair[A,B]})#F2]{
def map[B, C](pair: Pair[A, B])(f: B => C): Pair[A, C] = Pair[A, C](pair.first, f(pair.second))
}
If we use Pair to implement get, each get will recreate a new S only to discard it immediately. Efficiency may not be our main target but surely our user don't want that behaviour, especially for lenses where S is expected to be a nested case class. The trick here is to realise that we can construct a class with two type parameters with a single value. The second type will be free, i.e. it can be whatever we want. Let's call this type Const:
case class Const[A, B](get: A)
def constFunctor[A] = new Functor[({type F2[B] = Const[A,B]})#F2]{
def map[B, C](const: Const[A, B])(f: B => C): Const[A, C] = Const[A, C](const.get)
}
Our functor implementation discards the function f and modifies the second type parameter. Now, we can write get with Const:
def get(from: S): A = {
def store[B](a: A): Const[A, B] = Const[A, B](a)
def extract(const: Const[A, _]): A = const.get
type F2[B] = Const[A,B]
extract(lift[F2](from, {a: A => store[A](f(a)) }))
}
Or simply:
def get(from: S): A = lift[({type F2[b] = Constant[A,b]})#F2](from, {a: A => Constant[A, B](a)}).get
Final result
Here we are, we provided a default implementation for all methods of Lens except for lift. So our user will only have to define a single method in order to implement Lens.
trait Lens[S, A] { self =>
def lift[F[_]: Functor](from: S, f: A => F[A]): F[S]
def set(from: S, newValue: A): S = modify(from, _ => newValue)
def modify(from: S, f: A => A): S = lift(from, { a:A => Id(f(a)) }).get
def get(from: S): A = lift[({type F2[b] = Constant[A,b]})#F2](from, {a: A => Constant[A, B](a)}).get
def compose[B](other: Lens[A, B]): Lens[S, B] = ???
}
I let you write compose as an exercise (can you do it in a single line?)
Links:
- First part of Lens implementation
- Simon Peyton Jones presentation of Lens library at the London Scala exchange 2013
- Scalaz, Scala library that defines tones of nice abstraction
