Knows Not Much - 3 months ago 21
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 =
}
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))
}

case class Address(number: Int, street: String, city: String)
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)
``````

1. The purpose of the program is to compare two instances of the same case class. This is done via heterogenous lists (`HList`s), 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 `HList`s 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 `HList`s (`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 `HList`s., 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 `HList`s 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`.
Source (Stackoverflow)