Implicit parameter resolution for higher kinded types

9
votes

Consider the following code:

object foo {

    trait Bar[Q[_]]

    implicit object OptionBar extends Bar[Option]

    def test[T, C[_]](c: C[T])(implicit bar: Bar[C]) = ()

    def main(args: Array[String]) {
      test(Some(42): Option[Int])  //???
    }
}

This works, but I need to type the Some(42) as Option[Int], else the implicit object OptionBar won't be resolved (because a Bar[Some] is expected instead). Is there a way to avoid the explicit typing, so that I get the implicit OptionBar object in test even if I feed test with a Some or None?

[Clarification]

  • I used Option here just as example, it should also work if I have a Bar for an abstract class etc.
  • The solution should also work when other, unrelated Bars are in scope, say implicit object listBar extends Bar[list]

[Update]

It seems that making Bar's parameter contravariant does the trick:

object foo {

  trait Bar[-Q[_]] //<---------------

  implicit object OptionBar extends Bar[Option]
  implicit object ListBar extends Bar[List]

  def test[T, C[_]](c: C[T])(implicit bar: Bar[C]) = ()

  def main(args:Array[String]) {
    test(Some(42))
  }
}

But of course this is a severe limitation of the possibilities in Bar, so I still hope for a better answer.

2
scalaimplicithigher-kinded-types
Why is contravariance a severe limitation? Without using it, then Bar is invariant. If you're attempting to use Bar as a type-class against higher-kinded types that contravariance seems to fit in my mind. That is of course until you want to treat subclasses differently. However in that case, you still have other tricks, like implicit resolution "priorities" – jsuereth
@Josh: Consider something like trait Bar[Q[_]] { def zero[T]:Q[T] }, returing None and Nil in my examples. But I can't have such a method in Bar, if I define Q as contravariant. When you know how to solve this, please let me know... – Landei
Also, for a naturally contravariant type class, such as Equal[T], implicit search will favour Equal[Animal] over Equal[Dog]: scala-lang.org/node/4626. Inheritance and type classes are really tricky to mesh together. – retronym

2 Answers

7
votes

It's not going to work in all cases, but as stated, you can try this:

object foo {
  trait Bar[Q[_]]

  implicit object OptionBar extends Bar[Option]

  def test[T, C[_], D](c: D)(implicit bar: Bar[C], ev: D <:< C[T]) = ()

  def main(args: Array[String]) {
    test(Some(42)) //???
  }
}

Interestingly, this doesn't infer, although it expresses the same thing:

def test[T, C[_], D <: C[T]](c: D)(implicit bar: Bar[C]) = ()

To learn more about <:<, see:

5
votes

That's because Some(42) is a more specific type than Option[Int]. It is a Some[Int]. See alternative coding below:

object foo {

    trait Bar[Q[_]]

    implicit object OptionBar extends Bar[Option]

    def test[T, C[_]](c: C[T])(implicit bar: Bar[C]) = ()

    def main(args: Array[String]) {
      test(Option(42))
    }
}