What are the limitations on inference of higher-kinded types in Scala?

Question

In the following simplified sample code:

case class One[A](a: A) // An identity functor
case class Twice[F[_], A](a: F[A], b: F[A]) // A functor transformer
type Twice1[F[_]] = ({type L[α] = Twice[F, α]}) // We'll use Twice1[F]#L when we'd like to write Twice[F]

trait Applicative[F[_]] // Members omitted
val applicativeOne: Applicative[One] = null // Implementation omitted
def applicativeTwice[F[_]](implicit inner: Applicative[F]): Applicative[({type L[α] = Twice[F, α]})#L] = null

I can call applicativeTwice on applicativeOne, and type inference works, as soon as I try to call it on applicativeTwice(applicativeOne), inference fails:

val aOK = applicativeTwice(applicativeOne)
val bOK = applicativeTwice[Twice1[One]#L](applicativeTwice(applicativeOne))
val cFAILS = applicativeTwice(applicativeTwice(applicativeOne))

The errors in scala 2.10.0 are

- type mismatch; 
  found : tools.Two.Applicative[[α]tools.Two.Twice[tools.Two.One,α]]
  required: tools.Two.Applicative[F]
- no type parameters for method applicativeTwice: 
  (implicit inner: tools.Two.Applicative[F])tools.Two.Applicative[[α]tools.Two.Twice[F,α]]
  exist so that it can be applied to arguments 
  (tools.Two.Applicative[[α]tools.Two.Twice[tools.Two.One,α]]) 
  --- because --- 
  argument expression's type is not compatible with formal parameter type; 
     found : tools.Two.Applicative[[α]tools.Two.Twice[tools.Two.One,α]] 
     required: tools.Two.Applicative[?F]

Why wouldn't "?F" match with anything (of the right kind) ? Ultimately I'd like applicativeTwice to be an implicit function, but I'd have to get the type inference working first. I have seen similar questions, and the answers pointed to limitations in the type inference algorithms. But this case seems pretty limitative, and must be quite an annoyance in monad transformers, so I suspect I'm missing some trick to work around this.

Answer 1

You've hit a common annoyance: SI-2712. For clarity, I'm going to minimize your code a bit:

import language.higherKinds

object Test {
  case class Base[A](a: A)
  case class Recursive[F[_], A](fa: F[A])

  def main(args: Array[String]): Unit = {
    val one = Base(1)
    val two = Recursive(one)
    val three = Recursive(two) // doesn't compile
    println(three)
  }
}

This demonstrates the same type error as yours:

argument expression's type is not compatible with formal parameter type;
 found   : Test.Recursive[Test.Base,Int]
 required: ?F
        val three = Recursive(two) // doesn't compile
                    ^

First a bit of syntax and terminology you probably already know:

• In Scala we say that a plain, unparameterized data type (such as Int) has kind _. It's monomorphic.
• Base, on the other hand, is parameterized. we can't use it as the type of a value without providing the type it contains, so we say has kind _[_]. It's rank-1 polymorphic: a type constructor that takes a type.
• Recursive goes further still: it has two parameters, F[_] and A. The number of type parameters don't matter here, but their kinds do. F[_] is rank-1 polymorphic, so Recursive is rank-2 polymorphic: it's a type constructor that takes a type constructor.
• We call anything rank two or above higher-kinded, and this is where the fun starts.

Scala in general doesn't have trouble with higher-kinded types. This is one of several key features that distinguishes its type system from, say, Java's. But it does have trouble with partial application of type parameters when dealing with higher-kinded types.

Here's the problem: Recursive[F[_], A] has two type parameters. In your sample code, you did the "type lambda" trick to partially apply the first parameter, something like:

val one = Base(1)
val two = Recursive(one)
val three = {
  type λ[α] = Recursive[Base, α]
  Recursive(two : λ[Int])
}

This convinces the compiler that you're providing something of the correct kind (_[_]) to the Recursive constructor. If Scala had curried type parameter lists, I'd definitely have used that here:

case class Base[A](a: A)
case class Recursive[F[_]][A](fa: F[A]) // curried!

def main(args: Array[String]): Unit = {
  val one = Base(1)          // Base[Int]
  val two = Recursive(one)   // Recursive[Base][Int]
  val three = Recursive(two) // Recursive[Recursive[Base]][Int]
  println(three)
}

Alas, it does not (see SI-4719). So, to the best of my knowledge, the most common way of dealing with this problem is the "unapply trick," due to Miles Sabin. Here is a greatly simplified version of what appears in scalaz:

import language.higherKinds

trait Unapply[FA] {
  type F[_]
  type A
  def apply(fa: FA): F[A]
}

object Unapply {
  implicit def unapply[F0[_[_], _], G0[_], A0] = new Unapply[F0[G0, A0]] {
    type F[α] = F0[G0, α]
    type A = A0
    def apply(fa: F0[G0, A0]): F[A] = fa
  }
}

In somewhat hand-wavey terms, this Unapply construct is like a "first-class type lambda." We define a trait representing the assertion that some type FA can be decomposed into a type constructor F[_] and a type A. Then in its companion object, we can define implicits to provide specific decompositions for types of various kinds. I've only defined here the specific one that we need to make Recursive fit, but you could write others.

With this extra bit of plumbing, we can now do what we need:

import language.higherKinds

object Test {
  case class Base[A](a: A)
  case class Recursive[F[_], A](fa: F[A])

  object Recursive {
    def apply[FA](fa: FA)(implicit u: Unapply[FA]) = new Recursive(u(fa))
  }

  def main(args: Array[String]): Unit = {
    val one = Base(1)
    val two = Recursive(one)
    val three = Recursive(two)
    println(three)
  }
}

Ta-da! Now type inference works, and this compiles. As an exercise, I'd suggest you create an additional class:

case class RecursiveFlipped[A, F[_]](fa: F[A])

... which isn't really different from Recursive in any meaningful way, of course, but will again break type inference. Then define the additional plumbing needed to fix it. Good luck!

Edit

You asked for a less simplified version, something aware of type-classes. Some modification is required, but hopefully you can see the similarity. First, here's our upgraded Unapply:

import language.higherKinds

trait Unapply[TC[_[_]], FA] {
  type F[_]
  type A
  def TC: TC[F]
  def apply(fa: FA): F[A]
}

object Unapply {
  implicit def unapply[TC[_[_]], F0[_[_], _], G0[_], A0](implicit TC0: TC[({ type λ[α] = F0[G0, α] })#λ]) =
    new Unapply[TC, F0[G0, A0]] {
      type F[α] = F0[G0, α]
      type A = A0
      def TC = TC0
      def apply(fa: F0[G0, A0]): F[A] = fa
    }
}

Again, this is completely ripped off from scalaz. Now some sample code using it:

import language.{ implicitConversions, higherKinds }

object Test {

  // functor type class
  trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
  }

  // functor extension methods
  object Functor {
    implicit class FunctorOps[F[_], A](fa: F[A])(implicit F: Functor[F]) {
      def map[B](f: A => B) = F.map(fa)(f)
    }
    implicit def unapply[FA](fa: FA)(implicit u: Unapply[Functor, FA]) =
      new FunctorOps(u(fa))(u.TC)
  }

  // identity functor
  case class Id[A](value: A)
  object Id {
    implicit val idFunctor = new Functor[Id] {
      def map[A, B](fa: Id[A])(f: A => B) = Id(f(fa.value))
    }
  }

  // pair functor
  case class Pair[F[_], A](lhs: F[A], rhs: F[A])
  object Pair {
    implicit def pairFunctor[F[_]](implicit F: Functor[F]) = new Functor[({ type λ[α] = Pair[F, α] })#λ] {
      def map[A, B](fa: Pair[F, A])(f: A => B) = Pair(F.map(fa.lhs)(f), F.map(fa.rhs)(f))
    }
  }

  def main(args: Array[String]): Unit = {
    import Functor._
    val one = Id(1)
    val two = Pair(one, one) map { _ + 1 }
    val three = Pair(two, two) map { _ + 1 }
    println(three)
  }
}

Answer 2

Note (3 years later, July 2016), scala v2.12.0-M5 is starting to implement SI-2172 (support for higher order unification)

See commit 892a6d6 from Miles Sabin

-Xexperimental mode now only includes -Ypartial-unification

It follows Paul Chiusano's simple algorithm:

// Treat the type constructor as curried and partially applied, we treat a prefix
// as constants and solve for the suffix. For the example in the ticket, unifying
// M[A] with Int => Int this unifies as,
//
//   M[t] = [t][Int => t]  --> abstract on the right to match the expected arity
//   A = Int               --> capture the remainder on the left

The test/files/neg/t2712-1.scala includes:

package test

trait Two[A, B]

object Test {
  def foo[M[_], A](m: M[A]) = ()
  def test(ma: Two[Int, String]) = foo(ma) // should fail with -Ypartial-unification *disabled*
}

And (test/files/neg/t2712-2.scala):

package test

class X1
class X2
class X3

trait One[A]
trait Two[A, B]

class Foo extends Two[X1, X2] with One[X3]
object Test {
  def test1[M[_], A](x: M[A]): M[A] = x

  val foo = new Foo

  test1(foo): One[X3]     // fails with -Ypartial-unification enabled
  test1(foo): Two[X1, X2] // fails without -Ypartial-unification
}