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另一方面,参数化.我们不能在没有提供它包含的类型的情况下将它用作值的类型,所以我们说它有种类_[_].它是rank-1多态的:一个类型的类型构造函数.
• Recursive更进一步:它有两个参数,F[_]和A.类型参数的数量在这里并不重要,但它们的类型确实如此.F[_]是秩1多态性,所以Recursive是等级2的多态:这是一个类型的构造函数类型构造.
• 我们称任何等级为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有curried类型参数列表,我肯定在这里使用过:

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.然后在其伴随对象中,我们可以定义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)
  }
}