Lens implementation - Part 2

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:

1. First part of Lens implementation
2. Simon Peyton Jones presentation of Lens library at the London Scala exchange 2013
3. Scalaz, Scala library that defines tones of nice abstraction

Lens implementation - Part 1

Few months ago, I watched an amazing presentation given by Simon Peyton Jones [1] about how Edward Kmett implemented lenses in Haskell [2]. This talk was so inspiring that I started to port Edward's library in Scala with Monocle [3].

Today, I would like to start a series of blog posts to share the functional tricks Edward pulled off and how I implemented them in Scala. The code you will see below is not exactly how it is implemented in Monocle but it is close enough for people to make the bridge.

First of all, what is a lens?

A lens is often described as a pair of functions get and set between a type S and A, typically A is a component of S e.g. S is a person and A his age. They are two main advantages of using lenses instead of standard getters and setters. Firstly lenses compose, if you have a lens between A and B and a lens between B and C then you can compose the two to obtain a lens between A and C! Secondly, we can define many more high-level functions to update an A and rebuild S with the modified A. Let's have a look at Lens interface.

  
trait Lens[S, A] { self =>

  def get(from: S): A

  def set(from: S, newValue: A): S

  def modify(from: S, f: A => A): S

  def liftOption(from: S, f: A => Option[A]): Option[S]

  def liftFuture(from: S, f: A => Future[A]): Future[S]

  def liftList(from: S, f: A => List[A]): List[S]

  // and potentially other lift functions

  def compose[B](other: Lens[A, B]): Lens[S, B]
}

object Example {

  // I prepend accessor by _ to make it easier to use lenses 
  // than std accessors
  case class Location(_x: Int, _y: Int)
  case class Character(_name: String, _health: Int, _location: Location)

  // let say I have the following lenses defined
  val health  : Lens[Character, Int]      = ???
  val location: Lens[Character, Location] = ???
  val x, y    : Lens[Location, Int]       = ???

  val barbarian = Character("Krom" , 30, Location(8,13))
  
  health.get(barbarian)     // 30
  health.set(barbarian, 32) // Character("Krom" , 32, Location(8,13))

  health.modify(barbarian, _ + 1) 
  // Character("Krom" , 31, Location(8,13)) 
  
  (location compose x).liftList(barbarian, n => List(n - 1, n+ 1)) 
  // List(Character("Krom" , 30, Location(7,13))), 
  //      Character("Krom" , 30, Location(9,13)))
   
}

One reason people may want to use lenses is to remove boiler plate code when updating nested immutable objects. However, no one will ever use lenses if they are too complex to create or introduce more boiler plate (it kind of defeat the purpose!). Our quest to simplify lenses construction will start by providing default implementation for as many methods as possible. When we get that we can look at macros to generate the rest.

1. Lift functions

I defined three lift functions in Lens trait that are very similar. They all take an S and a function from A that lift A into a context (Option, List, Future) and finally return a lifted S. Let's have a look at how could we implement liftOption in order to extract a pattern.

  

def liftOption(from: S, f: A => Option[A]): Option[S] = {
  val a : A = get(from)         // extract A from S
  val optA : Option[A] = f(a)   // apply provided function
  optA match {                  // case analysis on optA
    case None           => None
    case Some(updatedA) => Some(set(from, updatedA)) 
    // if there is an updated A then build a new S with it
  }
}

Or simply:

  

def liftOption(from: S, f: A => Option[A]): Option[S] = 
  f(get(from)) map { newA => set(from, newA) }

We can see something interesting on the second version, we only use the method map from Option. In fact, if we try to implement liftFuture and liftList the implementation will be exactly the same! So we could refactor our three lift functions into one if we can find a general context F that defines map ... This is exactly a Functor!

  

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

// F[_] : Functor means that F is a type constructor
// such as there is an instance of Functor in scope
def lift[F[_] : Functor](from: S, f: A => F[A]): F[S] =
  Functor[F].map(f(get(from))){ newA => set(from, newA) } 

// to rewrite liftOption as lift we need to provide an instance of
// Functor for Option fortunately scalaz [4] does this for us
def liftOption(from: S, f: A => Option[A]): Option[S] = lift[Option](from, f)

def liftFuture(from: S, f: A => Future[A]): Future[S] = lift[Future](from, f)

def liftList(from: S, f: A => List[A]): List[S] = lift[List](from, f)

2. Set

Set can be seen as a specific case of modify where f is a constant function.

  

def set(from: S, newValue: A): S = {
  def constant(_: A): A = newValue
  modify(from, constant)
}

Or simply:

  

def set(from: S, newValue: A): S = modify(from, _ => newValue)

Sum up

We made a good progress today, we learnt what lenses are, we collapsed all our lift functions into one and rewrote set in terms of modify. So now to implement Lens we only need to define:

• get
• modify
• lift
• compose

Next week [5] we are going to simplify Lens definition even further. As a hint, I will quote Simon Peyton Jones there exist "one function to rule them all" but which one is it???

Links:

1. Simon Peyton Jones presentation of Lens library at the London Scala exchange 2013
2. Lens library in Haskell
3. Monocle, attempt to port lens library in Scala
4. Scalaz, Scala library that defines tones of nice abstraction
5. second part of Lens implementation