Shapeless : Computing deltas

A real life example

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)
			}
}