Knows Not Much Knows Not Much - 1 year ago 95
Scala Question

Hard to understand Shapeless code

I am trying to learn shapeless, However I find that Shapeless code is really hard to understand.

So I got this code example from a talk given on youtube.

Can anyone explain to me what is going on (step by step). The thing which I find most difficult is that everything is an implicit and so its really hard to trace the code ....

Also, please point me to some resources which can help me understand code like this. Everytime I encounter code with so many implicits I feel that I don't even know Scala.

import shapeless._

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)

trait SimpleDelta[R <: HList] extends DepFn2[R, R] {
type Out <: HList

object SimpleDelta {

type Aux[I <: HList, O <: HList] = SimpleDelta[I]{type Out = O}
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 =

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

SimpleDelta(homer, ned)

Answer Source
  1. The purpose of the program is to compare two instances of the same case class. This is done via heterogenous lists (HLists), which can function as generic representations of case classes. shapeless provides the infrastructure to convert between a case class and its generic HList representation. Note that in this example the difference is not calculated recursively, i.e. any nested case class instances will be compared atomically.
  2. Let's assume the Diff trait and companion object are fairly self-explanatory.
  3. The SimpleDelta trait defines a function with two arguments (DepFn2). The signature is (R, R) => Out. Furthermore, a constraint on the result type is declared: Out <: HList. This means that for all subtypes of SimpleDelta, the type member Out must be a subtype of HList.
  4. The object SimpleDelta defines a type Aux. You find more info on the Aux pattern on the web, e.g. here. In short, it functions as an alias for the SimpleDelta trait, allowing to express the Out type member using a type parameter.
  5. Now the SimpleDelta object defines two implicit methods hnilDelta and hconsDelta. Each of those methods represents one of the possible constuctors of HList, HNil and HCons. An HList A :: B :: HNil can also be read as ::(A, ::(B, HNil)) or HCons(A, HCons(B, HNil)). Using the two methods, the input HLists can be recursively deconstructed and processed. Based on the return types of these methods, the compiler knows which one to implicitly resolve when it encounters an implicit parameter of the type SimpleDelta[R]: When R has been inferred to HNil, it will invoke hnilDelta; when R has been inferred to Head :: Tail (or HCons(Head, Tail)) for some types Head and Tail, it will invoke hconsDelta.
  6. The hnilDelta method determines the delta between two empty HLists (HNil is the empty HList).
    1. Note that the Out type member is set to HNil, which is the type of the HNil object. The result is HNil, since there is no difference.
    2. The return type of the method is Aux[HNil, HNil]. As explained above, this is an alias for SimpleDelta[HNil] { type Out = HNil }. It tells the compiler to invoke this method if it encounters an implicit parameter of type SimpleDelta[R], and R has been inferred to HNil.
  7. The hconsDelta method determines the delta between two non-empty HLists., i.e. two HLists which are composed of a head element of type H and a tail list of type T.
    1. The type parameter DT denotes the HList subtype representing the delta of the tail list.
    2. Note the implicit parameter tailDelta :Aux[T, DT]. It conveys that the method must be able to determine the delta between the tails of the two lists l and r: tailDelta(l.tail, r.tail).
    3. The return type of the method is Aux[H::T, Diff[H] :: DT]. As explained above, this is an alias for SimpleDelta[H::T] { type Out = Diff[H] :: DT }. It tells the compiler to invoke this method if it encounters an implicit parameter of type SimpleDelta[R], and R has been inferred to H::T for some types H and T.
    4. The type member Out is set to Diff[H] :: DT, which is the HList type for the resulting difference.
    5. The apply method determines the difference between the two head elements and prepends it to the difference betwee the tail lists, which is calculated using the implicit parameter tailDelta (see above).
  8. The apply method takes care of converting the instances l and r of type A to their generic HList representations, and invokes a SimpleDelta on these HLists to calculate the difference.
    1. The type R is the generic HList representation of A. The implicit parameter genA: Generic.Aux[A, R] denotes that the method requires a conversion between A and R.
    2. Additionally, the method declares an implicit parameter delta: SimpleDelta[R]. This is required to calculate the difference between the two generic HList representations of l and r.
    3. The return type of the method is delta.Out. Note that a dependent type is used here since the actual Out type member of the delta parameter is not known – it depends on the actual type A and its HList representation R.

What happens when SimpleDelta(homer, ned) is compiled?

  1. The typed invocation is SimpleDelta.apply[Character, R](homer, ned).
  2. The compiler tries to find matching values for the implicit parameters genA: Generic.Aux[Character, R] and delta: SimpleDelta[R].
  3. shapeless provides the implicit Generic.Aux[A, R] for case classes A. This mechanism is rather complex and out of the scope of this question, but what is relevant is that the generic HList representation of type Character is String :: Int :: Address :: HNil, so the compiler can infer the type of genA to Generic.Aux[Character, String :: Int :: Address :: HNil]. This in turn means that the type variable R can be inferred to String :: Int :: Address :: HNil.
  4. Now that the type R is known, the compiler will try to resolve the implicit value for parameter delta: SimpleDelta[R], i.e. SimpleDelta[String :: Int :: Address :: HNil]. The current scope doesn't contain any implicit methods with this return type or values with this type, but the compiler will also consult the implicit scope of the parameter type SimpleDelta, which includes the companion object SimpleDelta (see section Implicit Parameters in the Scala documentation).
  5. The compiler searches the SimpleDelta object for values or methods which provide an object of type SimpleDelta[String :: Int :: Address :: HNil]. The only matching method is hconsDelta, so the compiler wires the parameter value delta to an invocation of this method. Note that the HList is decomposed into head and tail: hconsDelta[String, Int :: Address :: HNil, DT](implicit tailDelta: Aux[Int :: Address :: HNil, DT]).
  6. To fill in the implicit tailDelta parameter, the compiler will continue to find a matching implicit method. This way, the HList is recursively deconstructed until only HNil is left and hnilDelta is invoked.
  7. On the "way up", the DT type variable will be inferred to Diff[Int] :: Diff[Address] :: HNil, and the return type of hconsDelta to SimpleDelta[String :: Int :: Address :: HNil] {type Out = Diff[String] :: Diff[Int] :: Diff[Address] :: HNil]}. Thus, the return type of apply is inferred to Diff[String] :: Diff[Int] :: Diff[Address] :: HNil.
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download