Sunday 23 February 2014

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