Shapeless : Computing deltas -

This is the code and some personal notes from the Shapeless? - Easy! talk where Valentin Kasas explains in a great way an advanced example of a real life use case (with slides).

Computing deltas

Imagine we want to be able to determine what are the difference between two objects of the same type
For example, we need to know what have changed in our DB since the last backup
We need to be able to compute such deltas over a wide variety of classes, that are unrelated
Of course, doing this by hand for each and every class is not an option

Our diff representation

sealed trait Diff[A]

final case class Identical[A](value: A) extends Diff[A]

final case class Different[A](left: A, right: A) extends Diff[A]

object Diff {
  def apply[A](left: A, right: A): Diff[A] =
    if (left == right) Identical(left)
    		else       Different(left, right)
}

A first Delta implementation

We are creating a superclass here using DepFn . The return type differs according to the input type

trait SimpleDelta[R <: HList] extends DepFn2[R, R] {
  type Out <: HList //Result is bounded by HList
}

object SimpleDelta {

/** type alias Aux adds as a type parameter the return Type. 
  * It is convenient in order to constrain it 
  * by passing it as a type parameter.
  */
  type Aux[I <: HList, O <: HList] = SimpleDelta[I]{ type Out = O }

  //Recursive Algorithm
  implicit def hnilDelta: Aux[HNil, HNil] = new SimpleDelta[HNil] {
    
    type Out = HNil
    
    def apply(l: HNil, r: HNil): Out = HNil
  }

  implicit def hconsDelta[H, T <: HList, DT <: HList]
    (implicit tailDelta: Aux[T, DT]) : Aux[H::T, Diff[H] :: DT] =
    	new SimpleDelta[H :: T]{
    		type Out = Diff[H] :: DT
    		
            def apply(l: H :: T, r: H :: T) : Out =
      			Diff(l.head, r.head) :: tailDelta(l.tail, r.tail)
  		}
  
  def apply[A, R <: HList](l: A, r: A)
    (implicit genA: Generic.Aux[A, R],
              delta: SimpleDelta[R]): delta.Out = 
    				delta(genA.to(l), genA.to(r))
}

Lets try it out

case class Address(number: Int, street: String, city: String)

case class Character(name: String, age: Int, address: Address)

val homer = Character("Homer Simpson", 42, Address(742, "Evergreen Terrace", "Springfield"))

val ned = Character("Ned Flanders", 42, Address(744, "Evergreen Terrace", "Springfield"))

Going further

That’s quite nice, but still a bit coarse-grained
SimpleDelta doesn’t work on nested fields

trait Delta[R <: HList] extends DepFn2[R, R]{
  type Out <: HList
}
object Delta extends LowPriorityDelta {
  type Aux[R <: HList, O <: HList] = Delta[R]{type Out = O}
  implicit def hnilDelta: Aux[HNil, HNil] = new Delta[HNil] {
    override type Out = HNil
    override def apply(l: HNil, r: HNil): Out = HNil
  }

  /**
  * H is the type of the head, in this case it is a product
  * GH is the H as HList
  * DH is the type of the delta of the head (here goes the embedded diff)  
  * T is the type of the tail
  * DT is type of the tail delta
  */
  implicit def hconsGenDelta[H, GH <: HList, DH <: HList,  T <: HList, DT <: HList]
         // if there is a generic representation for the head
    (implicit genH: Generic.Aux[H, GH],
         // if I am able to compute the delta for these 
              nested: Delta.Aux[GH, DH],
         // if I am able to compute the delta of the tail
              tailDelta: Delta.Aux[T, DT])
    //then I am able to compute the delta of the whole list
    : Aux[H :: T, DH :: DT] = new Delta[H :: T] {
      override type Out = DH :: DT

      override def apply(l: H :: T, r: H :: T): Out =
        nested(genH.to(l.head), genH.to(r.head)) :: tailDelta(l.tail, r.tail)
    }
  
  def apply[A, R <: HList](l: A, r: A)
    (implicit genA: Generic.Aux[A, R],
              delta: Delta[R]) : delta.Out =
      delta(genA.to(l), genA.to(r))
}

//To handle types that don't have a generic type , like String, Int, etc
trait LowPriorityDelta {
  implicit def hconsDelta[H, T <: HList, DT <: HList]
    (implicit tailDelta: Delta.Aux[T, DT])
    : Delta.Aux[H :: T, Diff[H] :: DT] = new Delta[H :: T] {
      override type Out = Diff[H] :: DT
      override def apply(l: H :: T, r: H :: T): Out =
        Diff(l.head, r.head) :: tailDelta(l.tail, r.tail)
    }
}

Patcher

A typeclass that takes the generic representation of an object and a delta, modifies the generic representation using the delta

trait Patcher[R <: HList, P <: HList] {
  def apply(repr: R, patch: P): R
}

trait LowPriorityPatcher {
  
  implicit def hconsPatcher[H, T <: HList, PT <: HList]
  (implicit tailPatcher: Patcher[T, PT]): Patcher[H::T, Diff[H]::PT] = 
    new Patcher[H::T, Diff[H]::PT] {
    	override def apply(repr: H :: T, patch: Diff[H] :: PT): H :: T = {
      		val head = patch.head match {
        		case Identical(_) => repr.head
        		case Different(_, x) => x
      			}
      		head :: tailPatcher(repr.tail, patch.tail)
    	}
  }
}

object Patcher extends LowPriorityPatcher{

  def apply[A, R <: HList, P <: HList](value: A, patch: P)
  (implicit gen: Generic.Aux[A, R], patcher: Patcher[R, P]): A =
      gen.from(patcher(gen.to(value), patch))

  implicit def hnilPatcher: Patcher[HNil, HNil] = 
  	new Patcher[HNil, HNil]{
          override def apply(repr: HNil, patch: HNil): HNil = HNil
  	}

  implicit def hconsGenPatcher[H, GH <: HList, T <: HList, PH <: HList,
  PT <: HList]
  (implicit genH: Generic.Aux[H, GH],
    headPatcher: Patcher[GH, PH],
    tailPatcher: Patcher[T, PT]): Patcher[H::T, PH::PT] =
    	new Patcher[H::T, PH::PT] {
    		override def apply(repr: H :: T, patch: PH :: PT): H :: T =
				genH.from(headPatcher(genH.to(repr.head), patch.head)) :: tailPatcher(repr.tail, patch.tail)
			}
}