Shapeless : Computing deltas

A real life exemple

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