`Equiv` should compose


#1

Consider the following:

scala> case class Foo(i: Int, j: Int)
defined class Foo

scala> def foo[T : Equiv](a: T, b: T): Unit = { 
     |   if(implicitly[Equiv[T]].equiv(a,b)) 
     |     println("EQ!") 
     |   else 
     |     println("neq...") 
     | }
foo: [T](a: T, b: T)(implicit evidence$1: Equiv[T])Unit

scala> foo(Foo(1,2),Foo(1,2))
EQ!

scala> foo(Foo(1,2),Foo(3,2))
neq...

as expected, now let’s define a custom Equiv:

scala> :paste
// Entering paste mode (ctrl-D to finish)

case class Bar(i: Int, j: Int)
object Bar {
  implicit val equiv = new Equiv[Bar] { 
    override def equiv(a: Bar, b: Bar): Boolean = a.i == b.i
  }
}

// Exiting paste mode, now interpreting.

defined class Bar
defined object Bar

scala> foo(Bar(1,2),Bar(1,3))
EQ!

again, this is expected, but:

scala> foo(Option(Bar(1,2)),Option(Bar(1,3)))
neq...

scala> foo(Option(Bar(1,2)),Option(Bar(1,2)))
EQ!

as can be seen, Equiv[Bar] isn’t being invoked.
The reason is, that Option's implicit being resolved is:

trait OptionOrdering[T] extends Ordering[Option[T]] { … }
implicit def Option[T](implicit ord: Ordering[T]): Ordering[Option[T]] =
  new OptionOrdering[T] { val optionOrdering = ord }

Since Ordering extends PartialOrdering which extends Equiv.
both PartialOrdering & Ordering implementations override equiv:

trait PartialOrdering[T] extends Equiv[T] { 
  …
  def equiv(x: T, y: T): Boolean = lteq(x,y) && lteq(y,x)
  …
}
trait Ordering[T] extends Comparator[T] with PartialOrdering[T] with Serializable {
  …
  override def equiv(x: T, y: T): Boolean = compare(x, y) == 0
  …
}

Because of that, I think OptionOrdering's implementation should be changed.
this is the current implementation:

trait OptionOrdering[T] extends Ordering[Option[T]] {
  def optionOrdering: Ordering[T]
  def compare(x: Option[T], y: Option[T]) = (x, y) match {
    case (None, None)       => 0
    case (None, _)          => -1
    case (_, None)          => 1
    case (Some(x), Some(y)) => optionOrdering.compare(x, y)
  }
}

and I think that equiv should be added to OptionOrdering explicitly:

override def equiv(x: Option[T], y: Option[T]): Boolean = {
  if(x.isEmpty) y.isEmpty
  else y.fold(false){ t =>
    implicitly[Equiv[T]].equiv(x.get,t)
  }
}

This should be fine, since Equiv companion extends LowPriorityEquiv which will handle any T thanks to universal.

Also, like Option, other Ordering implicits should get the same treatment (seqDerivedOrdering,Iterable,Tuple2,…,Tuple9).


#2

Is the problem not that whether you request an implicit Equiv[Option[T]] or an Ordering[Option[T]], the instance that you get is always based on an Ordering[T]? So your custom Equiv[Bar] will never be considered.

The implicit def Option should, in theory, have this signature:

implicit def Option[T, F[x] <: Equiv[x]](implicit f: F[T]): F[Option[T]] = ???

Either literally this, or perhaps something equivalent but implemented through some complicated implicit priority scheme.


#3

can’t it be simplified to:

implicit def Option[T : Equiv](implicit ord: Ordering[T]): Ordering[Option[T]] = …

?

In any case, changing the signature of the method breaks binary compatabillity, so that’s why I only call implicitly in the body.
I guess that in the next minor/major version we can introduce the API change.
but for maybe a patch for 2.12 / 2.11, this is the best I could think of…


#4

If you call implicitly[Equiv[T]] in the body you will only ever find an Equiv[Any] or something similar, not your custum implementation.

And if def Option promises to return an Ordering[Option[T]] it can’t really use an Equiv[T] anyway.


#5

in the case I present in the original post, I have Equiv in Bar's companion object, thus it takes precedence over Equiv[Any].

You are right that callers who want to override the default resolved implicit by importing / creating local in-block implicit value / etc’… won’t be able to benefit this change.

perhaps you are right.
My take on this, is to improve what we can without breaking binary compatabillity in 2.11 and 2.12,
and introduce a better solution (like yours) in 2.13 and forward.


#6

As far as I can see any real improvement at all would require breaking binary compatibility.
For 2.13, it’s probably to late already for any big changes, but a lot of things have already happened in this area, and it seems like the case you mentioned has effectively improved:

scala 2.13.0-pre-59975bb> foo(Option(Bar(1,2)),Option(Bar(1,3)))
EQ!

#7

good to know!
(I’m stuck with 2.11 in some of the projects, so won’t be able to benefit from this in said projects though…)


#8

I believe this should be re-labelled. It’s neither language design nor a SIP proposal. It should be labelled Scala Core instead.


#9

Done.


#10

Unless you have an implicit Ordering[Bar] defined that you didn’t mention, then Ordering[Option[Bar]] isn’t what’s being summoned for your Equiv. You are getting the implicit universalEquiv, for which the two values are not equiv because they are not == (see the REPL dump at the end for more detail).

Your suggested override of OptionOrdering#equiv will either just summon the Ordering[T] for the element or the universalEquiv (I’m not sure which without testing it) - if the former, it will do what it already does (and what you want); if the latter, you will get the same bad result you are currently getting. Either way, it is not necessary or an improvement.

If you create an implicit Ordering[Bar] that is consistent with the Equiv you defined, and then use Ordering[Option[Bar]]#equiv to compare the values, you should find it treats them correctly.

Welcome to Scala 2.12.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_201).
Type in expressions for evaluation. Or try :help.

scala> :paste
// Entering paste mode (ctrl-D to finish)

final case class Bar(i: Int, j: Int)
object Bar {
  implicit val ord: Ordering[Bar] = Ordering.by(_.i)
}

// Exiting paste mode, now interpreting.

defined class Bar
defined object Bar

scala> Ordering[Option[Bar]].equiv(Some(Bar(1, 2)), Some(Bar(1, 3)))
res0: Boolean = true

By typing //print and then hitting [TAB] in the REPL, we can see the universalEquiv being summoned.

scala> def test[A: Equiv](x: A, y: A): Boolean = Equiv[A].equiv(x, y)
test: [A](x: A, y: A)(implicit evidence$1: Equiv[A])Boolean

scala> :paste
// Entering paste mode (ctrl-D to finish)

case class Bar(i: Int, j: Int)
object Bar {
  implicit val equiv = new Equiv[Bar] {
    override def equiv(a: Bar, b: Bar): Boolean = a.i == b.i
  }
}

// Exiting paste mode, now interpreting.

defined class Bar
defined object Bar

scala> test(Bar(1, 2), Bar(1, 3)) //print
   test[Bar](Bar.apply(1, 2), Bar.apply(1, 3))(this.Bar.equiv) // : Boolean

scala> test(Bar(1, 2), Bar(1, 3))
res0: Boolean = true

scala> test(Some(Bar(1, 2)), Some(Bar(1, 3))) //print

test[Some[Bar]](scala.Some.apply[Bar](Bar.apply(1, 2)), scala.Some.apply[Bar](Bar.apply(1, 3)))(scala.math.Equiv.universalEquiv[Some[Bar]]) // : Boolean

scala> test(Some(Bar(1, 2)), Some(Bar(1, 3)))
res1: Boolean = false

#11

In 2.13, the universalEquiv is deprecated (and it will be removed as an implicit in 2.14); on top of this, we have added all the implicit Equiv generators that you find on Ordering, with a higher priority than the universalEquiv. Consequently, your example will work correctly as you expect it to in 2.13.


#12

The thing is, the classes I use, unlike the toy example, doesn’t have a defined order, and I wouldn’t know how to create an Ordering for it. Also, I can create an Equiv for my type T and Option[T], but I would likely also need it for Seq[T], Set[T], etc’… And I don’t want to define all those instances, and import it everywhere (since I obviously can’t put it on e.g. Option's companion, or Equiv's…

I’m glad it’s solved in 2.13, but what should users who are stuck with older versions do?


#13

You could try replacing it with cats Eq which provides similar functionality.


#14

Unfortunately, I can’t think of any other way to do it. You can mitigate the pain of defining all those instances by just copying the code from 2.13. You might be able to get around having to import it everywhere by setting it as a predef in your build? Not sure.

I will second Jasper’s suggestion of using a similar typeclass from a library like cats.