Ответ 1

Вы столкнулись с общим раздражением: SI-2712. Для ясности я немного скрою ваш код:

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)
  }
}

Это демонстрирует ту же ошибку типа, что и у вас:

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

Сначала немного синтаксиса и терминологии, которые вы, вероятно, уже знаете:

• В Scala мы говорим, что простой, непараметризированный тип данных (например, Int) имеет вид _. Это мономорфный.
• Base, с другой стороны, параметризуется. мы не можем использовать его как тип значения без указания типа, который он содержит, поэтому мы говорим, что имеет добрый _[_]. Это rank-1 polymorphic: конструктор типа, который принимает тип.
• Recursive идет еще дальше: он имеет два параметра: F[_] и A. Количество параметров типа здесь не имеет значения, но их виды. F[_] является полиморфным ранга 1, поэтому Recursive является rank-2 polymorphic: это конструктор типа, который принимает конструктор типа.
• Мы называем что-либо ранг два или выше более высокий, и именно здесь начинается забава.

Scala в общем случае не имеет проблем с типами более высокого класса. Это одна из нескольких ключевых особенностей, которая отличает систему своего типа от, скажем, Java. Но у него есть проблемы с частичным применением параметров типа при работе с более высокоподобными типами.

Здесь проблема: Recursive[F[_], A] имеет два типа параметров. В вашем примере кода вы применили трюк типа "лямбда", чтобы частично применить первый параметр, например:

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

Это убеждает компилятор, что вы предоставляете что-то вроде правильного типа (_[_]) конструктору Recursive. Если у Scala были типы параметров типов типов, я определенно использовал бы это здесь:

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)
}

Увы, это не так (см. SI-4719). Итак, насколько мне известно, наиболее распространенным способом решения этой проблемы является "неприемлемый трюк" из-за Майлза Сабина. Вот очень упрощенная версия того, что появляется в 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
  }
}

В несколько ручных терминах эта конструкция Unapply похожа на "класс lambda первого класса". Мы определяем черту, представляющую утверждение о том, что некоторый тип FA можно разложить на конструктор типа F[_] и тип A. Затем в своем сопутствующем объекте мы можем определить implicits для обеспечения конкретных разложений для типов различных типов. Я только определил здесь конкретный, который нам нужно сделать Recursive, но вы могли бы написать другие.

С помощью этой дополнительной части сантехники мы теперь можем делать то, что нам нужно:

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)
  }
}

Та-да! Теперь тип вывода работает, и это компилируется. В качестве упражнения я предлагаю вам создать дополнительный класс:

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

..., который действительно не отличается от Recursive каким-либо значимым образом, конечно, но снова нарушит вывод типа. Затем определите дополнительную сантехнику, необходимую для ее исправления. Удачи!

Изменить

Вы попросили менее упрощенную версию, что-то известно о типах. Требуется некоторая модификация, но, надеюсь, вы увидите сходство. Во-первых, здесь обновлен 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
    }
}

Опять же, это полностью сорвано с scalaz. Теперь используйте несколько примеров кода:

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)
  }
}

Ответ 2

Примечание (3 года спустя, июль 2016 года), scala v2.12.0-M5 начинает реализовывать SI-2172 (поддержка унификации более высокого порядка)

См. commit 892a6d6 из Майлз Сабин

-Xexperimental теперь включает только -Ypartial-unification

Из Paul Chiusano простой алгоритм:

// 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

test/files/neg/t2712-1.scala включает в себя:

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*
}

И (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
}