Attempt to implement type classes without inheritance

[julien-truffaut]

in scalaz and cats, type classes are defined as trait with inheritance to express facts like all Monad are an Applicative. This leads to some ambiguous implicit resolutions and as far as I know, the solution is to create a hierarchy of traits to guide implicit search. It also creates ambiguous implicit when you have two imports that brings the same implicit in scope e.g.

import scalaz.syntax.traverse._ 
import scalaz.syntax.foldable._

I wonder if it would be possible and desirable to implement type classes using abstract class and implicit evidence to express the hierarchy between two type classes:

abstract class Equal[T]{
  def eq(v1: T, v2: T): Boolean
}

object Equal{
  def apply[T](implicit ev: Equal[T]): Equal[T] = ev
  def equalA[T]: Equal[T] = new Equal[T] {
    def eq(v1: T, v2: T): Boolean = v1 == v2
  }

  implicit val intEqual = equalA[Int]
}

abstract class Ord[T: Equal]{
  def lowerThan(v1: T, v2: T): Boolean
  def lowerThanOEqual(v1: T, v2: T): Boolean = lowerThan(v1, v2) || Equal[T].eq(v1, v2)
  def greaterThan(v1: T, v2: T): Boolean = !lowerThan(v1, v2)
  def greaterThanOEqual(v1: T, v2: T): Boolean = greaterThan(v1, v2) || Equal[T].eq(v1, v2)
}

object Ord{
  def apply[T](implicit ev: Ord[T]): Ord[T] = ev
  def fromLowerThan[T: Equal](lth: (T, T) => Boolean): Ord[T] = new Ord[T] {
    def lowerThan(v1: T, v2: T) = lth(v1, v2)
  }

  implicit val intOrd = fromLowerThan[Int](_ < _)
}

I haven't tried this technique extensively, so it might in fact causes more issues that inheritance. However, I thought it make sense to discuss this option since you are just starting cats.

[ceedubs]

I seem to recall that the main reason scalaz didn't take this approach was because of the extra overhead of all of the implicit chaining (the extra function calls and instance allocations). I'm not sure how much of a problem this is in practice. Also for what it's worth, I think that I heard @tpolecat say that scalaz has considered taking this approach in scalaz 8.0.

[tpolecat]

I like the idea in principle but I also worry about allocations. Seems like it's worth prototyping.

[non]

I'm pretty skeptical (as I said on #71). I think the nested field lookups for every single method call will be really bad for performance. I think this strategy is a non-starter for Spire and Algebra.

If we did some testing and found that for Cats it would be OK, then we could move to it, but would have to drop interop with Algebra and Spire. I'm pretty reluctant to do this but willing to talk about it.

[julien-truffaut]

@non I understand and share your concern regarding the performance of using evidence. I will try to benchmark the two approach at some point.

Should I close this ticket until we have evidence that a non inheritance base approach provide good performance?

[ceedubs]

I just added the "on hold" label. I don't think we need to completely close the issue if it's still under consideration. If it sits here and rots for months then we can close it out.

[julien-truffaut]

@ceedubs sounds like a plan

[non]

Sounds good to me too.

[julien-truffaut]

people are experimenting removing inheritance in scalaz 8:
https://github.com/scalaz/scalaz/blob/37d7c9c8746a1a47f5f05c465f29938654fda838/core/src/main/scala/Order.scala

[retronym]

I tried both approaches in the lead up to Scalaz 7, but found it the inheritance free version was unworkable.

def foo[F: Functor]
def bar[F: Monad] = foo // will not typecheck

Adding an "upcasting" implicit from Monad[F] => Functor[F] seems to work until you extend the hierarchy beyond a depth of 2, or, worse, introduce diamonds.

[non]

@julien-truffaut there hasn't been any discussion on this issue. Do you want to keep it open? Are there concrete proposals to move forward?

[julien-truffaut]

No we didn't have any discussion regarding this issue recently. So it is better to close it for the moment.

I think scalaz 8 is looking toward this approach, we can always monitor how does it go.