scala - Scala 中高级类型的推理有哪些限制？

Question

在下面的简化示例代码中:

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

我可以在 applicativeOne 上调用 applicativeTwice，并且类型推断有效，一旦我尝试在 applicativeTwice(applicativeOne) 上调用它，推断就会失败:

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

scala 2.10.0 中的错误是

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

为什么“?F”不能与任何内容(正确类型的)匹配？最终我希望 applicativeTwice 成为一个隐式函数，但我必须首先让类型推断工作。我见过类似的问题，答案指出了类型推断算法的局限性。但这种情况似乎相当有限，并且在 monad 转换器中一定是相当烦人的，所以我怀疑我错过了一些解决这个问题的技巧。

Answer 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's 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另一方面，是参数化的。如果不提供它包含的类型，我们就不能将它用作值的类型，所以我们说 has kind _[_] 。它是1 级多态:采用类型的类型构造函数。
• Recursive更进一步:它有两个参数，F[_]和A 。类型参数的数量在这里并不重要，重要的是它们的种类。 F[_]是 1 级多态性，所以 Recursive是2 级多态:它是一个采用类型构造函数的类型构造函数。
• 我们将任何等级为二级或以上的事物称为高级，这就是乐趣的开始。

Scala 一般来说，在处理更高种类的类型时不会遇到问题。这是将其类型系统与 Java 等类型系统区分开来的几个关键特性之一。但在处理更高种类的类型时，它确实在类型参数的部分应用方面存在问题。

问题是:Recursive[F[_], A]有两个类型参数。在示例代码中，您使用了“type lambda”技巧来部分应用第一个参数，例如:

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

这使编译器相信您正在向 _[_] 提供正确类型的内容 ( Recursive )构造函数。如果 Scala 有柯里化(Currying)类型参数列表，我肯定会在这里使用它:

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)。因此，据我所知，处理此问题的最常见方法是迈尔斯·萨宾 (Miles Sabin) 提出的“不应用技巧”。这是 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 。然后在它的伴生对象中，我们可以定义隐式来为各种类型提供特定的分解。我在这里只定义了我们需要制作的具体一个 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
    }
}

这又是completely ripped off from 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)
  }
}