Extractors

[greenbergjosh]

I have played with the sample code, but I don't quite understand how the example works. I believe I am missing something about Scala implicits, but I think it may be more than that. Here is my code. It can be dropped directly into a scala fiddle.

final case class Eq[A](equal: (A, A) => Boolean) 
object Eq { 
  implicit class EqOps[A: Eq](a: A) { 
    def ===(b: A): Boolean = implicitly[Eq[A]].equal(a, b) 
  } 
  // Use type-specific comparisons to define some typeclass instances here: 
  implicit val eqInt: Eq[Int] = Eq[Int]({
    case (a1:Int, a2:Int) =>
      println("Int start")
      val b:Boolean = (a1 == a2)
      //val b:Boolean = (_ == _)
      println("Int end")
      b
    }) 
  implicit val eqString: Eq[String] = Eq[String](_ == _) 
  implicit def eqPair[A: Eq, B: Eq] = Eq[(A, B)] { 
    case ((a1, b1), (a2, b2)) => a1 === a2 && b1 === b2 
  }
  implicit def eqEither[A: Eq, B: Eq] = Eq[Either[A, B]] { 
    case (Left(a1), Left(a2)) => 
      println("Case either left start")
      val b = a1 === a2 // Compare a1 + 0 and a2 + 0. 
      println("Case either left end")
      b
    case (Right(b1), Right(b2)) => 
      println("Case either right start")
      val b = (b1 === b2) // Compare 0 + b1 and 0 + b2. 
      println("Case either right end")
      b
    case _ => 
      println("Case either false")
      false // a + 0 is never equal to 0 + b. 
  }
}

import Eq._

type R[A] = Either[Int, A]
def eqR[A](implicit ti: Eq[A]): Eq[R[A]] = {
  println("typeRStart")
  val b = eqEither[Int, A]
  println("typeREnd")
  println(b)
  b
}

final case class V(r: R[V])
implicit def eqV : Eq[V] = Eq {
  case (V(r1), V(r2)) =>
    println("typeVStart")
    val b = eqR(eqV).equal(r1, r2) 
    println("typeVEnd")
    b
}

val v1 = V(Right(V(Left(1))))
val v2 = V(Right(V(Left(2))))
val v3 = V(Left(1))
println("---Start---")
println(v1===v2)
println("---------")

// End of code

The code is very similar to your code, except I have added in some println statements and simplified the recursive type. I am struggling with the following two lines:

def eqR[A](implicit ti: Eq[A]): Eq[R[A]] { // Call this line 1 ... val b = eqEither[Int, A] // call this line 3 ... } --and-- val b = eqR(eqV).equal(r1, r2) // Call this line 2

It would seem that there is no need to make ti implicit in line 1. In fact, it would seem there is no need for ti at all since it is not used in the body of eqR at all. However, it looks like ti is essentially telling eqR that A must be Eq-able - kind of like a type constraint or a parameter to what you call a PTVF. Also, since line 2 always explicitly passes eqV for eqR it again feels like I could remove the implicit specifier from line 1 (since it is always passed explicitly on line2), but, of course, I cannot.

In truth, I can't really seem to make heads or tails of those lines at all. Clearly, eqR is not like eqInt or eqString or any of the other eqX methods. They all construct an Eq by providing an implementation for equals, whereas eqR returns an Eq[R[A]]. It sort of looks like eqR lifts an Eq[A] into an eqR[A]] so that eqV can then use the specific implementation of that eqR[A]].equals.

Unfortunately, how this works, which is clearly based on ti in line 1 and the fact that ti is implicit, is still a complete mystery. I think this line

val b = eqEither[Int, A]

Is calling a function with an implicit parameter but I don't see where or what the implicit is or how it fits together or why it is needed. Maybe this even ties into why you had

implicit val e1 = … implicit val e2 = …

in your version of the code. Those make no sense to me either. There seems to be some Scala magic happening here. This is my first exposure to Scala, but this makes me dislike it. I bounced the question off of a few other developers and they were equally stumped - granted, none of us had ever seen Scala before. I'll shutdown my rant on believing that good code is clear and not magic and just say that it's my own lack of experience as opposed to poor language design. Regardless, I suspect that others will likely run into similar questions if they actually try to comprehend the code as opposed to simply mimicking it.

What would be helpful would be a diagram that shows, every step of the way

1. What things have been placed in the ether (I mean into implicit scope)
2. What is calling what (the runtime tree of calls that I have produced with printlns)
3. What type is eqV in line 2 on each execution of line 2
4. What is the type of ti on line 1 for each execution, where does it come from, why is it implicit
5. What is actually happening on line 3

Thank you for your help.

[greenbergjosh]

So, I figured I would read from the start of the chapter again. You mention:

def f[A, B](args...)(implicit t1: Typeclass1[A], t2: Typeclass2[B])
is equivalent to the shorter code
def f[A: Typeclass1, B: Typeclass2](args...)

That clarifies the use of implicit. It really does just set a constraint on A, so the following change:

//def eqR[A](implicit ti: Eq[A]): Eq[R[A]] = {
def eqR[A : Eq]: Eq[R[A]] = {

works just as well. I prefer the latter syntax, but I suppose I am just used to it from other languages. I see that we don't need ti in this case, but in your earlier examples we did.

Of course, now, eqR does not seem to take any arguments, but when we call it as in

val b = eqR(eqV).equal(r1, r2)

it does take an argument, namely eqV. So, I suppose that might be why the implicit agument syntax is prefered, since it clearly shows that there is an argument being passed. This still leaves me stuck on my question 3...

I also fiddled with some other sample code:

implicit def testVal : Int = {
  val r = scala.util.Random
  r.nextInt
  //1
}

Using this I proved to myself (hopefully correctly) that:

val b = eqEither[Int, A]

Is actually going to construct a new, distinct instance of eqEither[Int, A] each time it is called. We don't really need a new instance every time, since it contains only methods, but I believe that is what is happening.

If that is all correct, then I can somewhat begin to answer my own questions:

1. What things have been placed in the ether (I mean into implicit scope) Nothing specifically on behalf of val b = eqEither[Int, A] At least, I don't think anything is needed in implicit scope for that line to run. Well, that's wrong, we must have implicit val eqInt: Eq[Int] = Eq[Int]({ … }) in the implicit scope. I believe this ensures that the Int in Either[Int, A] matches the A : Eq when trying to find implicit def eqEither[A: Eq, B: Eq]
2. What is calling what (the runtime tree of calls that I have produced with printlns) This is fairly clear from the printlns
3. What type is eqV in line 2 on each execution of line 2
4. What is the type of ti on line 1 for each execution, where does it come from, why is it implicit This question goes away. It's just a syntactic thing.
5. What is actually happening on line 3 This too is answered, we just are calling the eqEither typeclass instance which I believe constructs us an instance of an Eq[Int, A] - in other words it gives us an object with an equals method on it

I think that just leaves question 3. I'll see if I can figure that one out next.

[winitzki]

You have raised a lot of questions, so let me begin answering one by one.

First, does val b = eqEither[Int, A] require any implicits or not?

To answer this, we have to look at the definition of eqEither.

implicit def eqEither[A: Eq, B: Eq] = Eq[Either[A, B]] { ... }

Scala syntax [A: Eq, B: Eq] means that eqEither , despite appearances, actually takes two implicit arguments of types Eq[A] and Eq[B]. An equivalent syntax is

implicit def eqEither[A, B](implicit ev1: Eq[A], ev2: Eq[B]) = Eq[Either[A, B]] { ... }

So, eqEither[Int, A] will not compile unless we have a value of type Eq[Int] and a value of type Eq[A] in the implicit scope. The only way of using eqEither[Int, A] is to define those values as implicits first:

implicit val eqInt: Eq[Int] = ...
implicit val eqA: Eq[A] = ... // whatever A is
val b = eqEither[Int, A]  // Now this compiles.

The syntax

def eqR[A](implicit ti: Eq[A]): Eq[R[A]] = ...

is equivalent to

def eqR[A: Eq]: Eq[R[A]] = ...

Second, I do not agree that "Clearly, eqR is not like eqInt or eqString or any of the other eqX methods. They all construct an Eq by providing an implementation for equals, whereas eqR returns an Eq[R[A]]" as you say. In my view, they are all similar: they are instance values (or "evidence values") showing that a certain type belongs to the typeclass. The value eqInt has type Eq[Int], and the value eqR[A] has type Eq[R[A]].

"They all construct an Eq by providing an implementation for equals, whereas eqR returns an Eq[R[A]]"

I would say, they all construct an Eq by providing an implementation for equals. However, eqInt provides that implementation directly, while eqR calls a helper function, eqEither, that in turn provides an implementation for equals.

[winitzki]

What type is eqV in line 2 on each execution of line 2

The type is always the same: Eq[V]. The type V does not change.

_val b = eqEither[Int, A] Is actually going to construct a new, distinct instance of eqEither[Int, A] each time it is called`

Yes, that's unfortunately true - and necessary. We can't have a fixed value of type eqEither[Int, A] because the type A can be different every time we call that function. Values (val) cannot have type parameters in Scala. In this case, we don't really need to create any values of type A but we need an implicit argument of type Eq[A], which is going to be different for different As. We can't precompute in advance all possible values for all possible types A. So, we have to make it a def and return a new value each time.

[greenbergjosh]

Forgive me for pressing the issue, but I read your thoughtful and truly appreciated replies, and I find that I still do not agree. Specifically, in regards to eqR being different from eqInt or eqString. The syntax took me a few tries, but here is the code to show what I feel truly creates an analogous implementation of eqR. In this example (and I apologize for any confusion it may cause), I have used the name eqSofA to represent what was eqR in my code (above) and what was eqS in your book. The new function eqSofA is a truly analogous implementation of Eq for S[A]. It has effectively eliminated all of the parts of the code that I did not like. In particular, I no longer need a call like eqS(eqT).equals and (as I mentioned in the other issue I opened), I also don't need the eN subexpressions. The code is shorter, follows a consistent pattern (which was broken by eqS(eqT)), and still seems to work. Of course, it is quite possible that my code isn't correct. However, if it is, I might argue that it better captures the spirit of your exposition. I am very anxious to hear your thoughts, and I hope I have not overstepped in any way.

final case class Eq[A](equal: (A, A) => Boolean) 
object Eq { 
  implicit class EqOps[A: Eq](a: A) { 
    def ===(b: A): Boolean = implicitly[Eq[A]].equal(a, b) 
  } 
  // Use type-specific comparisons to define some typeclass instances here: 
  implicit val eqInt: Eq[Int] = Eq[Int](_ == _)
  implicit val eqString: Eq[String] = Eq[String](_ == _) 
  implicit def eqPair[A: Eq, B: Eq] = Eq[(A, B)] { 
    case ((a1, b1), (a2, b2)) => a1 === a2 && b1 === b2 
  }
  implicit def eqEither[A: Eq, B: Eq] = Eq[Either[A, B]] { 
    case (Left(a1), Left(a2)) => a1 === a2 // Compare a1 + 0 and a2 + 0. 
    case (Right(b1), Right(b2)) => (b1 === b2) // Compare 0 + b1 and 0 + b2. 
    case _ => 
      false // a + 0 is never equal to 0 + b. 
  }
}

import Eq._
type S[A] = Either[Either[Int, A], (Int, (A, A))] 
def eqSofA[A: Eq] = Eq[S[A]] { 
  case (s1, s2) => eqEither[Either[Int, A], (Int, (A, A))].equal(s1, s2)
}

final case class T(s: S[T])
implicit def eqT: Eq[T] = Eq { 
  case (T(s1), T(s2)) => s1 === s2
}

val t1 = T(Left(Right(T(Left(Left(10)))))) 
val t2 = T(Left(Right(T(Left(Left(10)))))) 

val t3 = T(Left(Right(T(Right( (5, (T(Left(Left(10))),T(Left(Left(11))))) ))))) 
val t4 = T(Left(Right(T(Right( (5, (T(Left(Left(10))),T(Left(Left(11))))) ))))) 

println(t1===t2)
println(t3===t4)

[winitzki]

I added a comment to the other issue; will return to this discussion when time permits.

[winitzki]

1. I think I now understand what you meant when you said "eqS works differently than all other functions such as eqInt, eqEither, etc." What you meant is that eqInt defines the equals function directly, so that the code looks like

val eqInt = Eq[Int] { case (x, y) => ... }

So, you want to define eqS in the same way, using code that looks like this,

def eqS[A: Eq] = Eq[S[A]] { case (s1, s2) => ... }

Indeed, you can write code in this way. You wrote it as

def eqSofA[A: Eq] = Eq[S[A]] { 
  case (s1, s2) => eqEither[Either[Int, A], (Int, (A, A))].equal(s1, s2)
}

If you compare this code with the code currently in the book but omitting ev1, ev2, ev3, which we can omit as already discussed:

def eqS[A](implicit ti: Eq[A]): Eq[S[A]] = eqEither[Either[Int, A], (Int, (A, A))]

you will notice that they are equivalent, but your code expands the function inside Eq while my code does not. In other words, simplifying the names, your code vs. my code is like this:

def f(ev: Eq[X]): Eq[Y] = Eq[Y] { case (a, b) => g.equals(a, b)   // Your code.
def f(ev: Eq[X]): Eq[Y] = g                                       // My code.

You expanded the value g: Eq[Y] into an equivalent expression Eq[Y](case (a, b) => g.equals(a, b)). This is like expanding a case class C(x: Int): a value c: C is equivalent to C(c.x).

There remains the question - what is better to put into the book, your expanded version or my non-expanded version. I'm not sure, but it seems to me that the non-expanded version (after deleting ev1, ev2, ev3) is easier to understand because it shows directly how to get the required value. Yet you had trouble understanding this logic. Maybe what is missing is a more detailed explanation about how the Scala compiler finds implicit values when a function requires them.

2. Your version of eqT seems more confusing to me because it hides the fact that there is recursion going on - i.e. that eqT is a recursively defined value and, for example, cannot be defined as a val. My version of the code makes this fact obvious. Your version of the code hides it under three steps of indirection: eqT defines a new value of type Eq[T], which uses the === operation, which calls the .equals method, which uses some eqSofA[A], which requires the A: Eq constraint, but here we must have A = T, so a value of type Eq[A] is actually Eq[T], -- that is, the same eqT we are trying to define. I don't think I will put that code into the book.

[winitzki]

Maybe you can summarize the remaining questions after you look this over? I am not sure what next to answer, and maybe you have new questions after reading my replies.