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

斯卡拉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 
        ^

首先一点语法和词汇的你可能已经知道：

• 在斯卡拉我们说一个简单的，未参数化的数据类型（如Int）有种类_。它是单态。
• Base另一方面，被参数化。我们不能使用它作为值的类型而不提供它所包含的类型，所以我们说有种类_[_]。它是rank-1多态性：一种类型构造函数，它需要一个类型。
• Recursive更进一步：它有两个参数，F[_]和A。类型参数的数量在这里并不重要，但是它们的类型可以。 F[_]是rank-1多态，所以Recursive是rank-2多态：它是一个类型构造函数，它需要一个类型构造函数。
• 我们称之为高等级任何等级二或以上，这是乐趣开始的地方。

斯卡拉一般不会遇到较高接触类型的问题。这是区分类型系统和Java的几个关键特性之一。但是在处理更高版本的类型时，类型参数的部分应用确实有问题。

问题出在这里：Recursive[F[_], A]有两个类型参数。在你的示例代码，你做的“类型拉姆达”招部分申请的第一个参数，是这样的：

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

这说服，你到Recursive提供正确的种类（_[_]）的东西编译构造函数。如果斯卡拉已经咖喱类型的参数列表，我肯定已经用在这里：

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构造就像是一个“一流的类型拉姆达”。我们定义了一个特征，表示某种类型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) 
    } 
} 

Answer 2

注（3年后，2016年7月），scala v2.12.0-M5开始实施SI-2172（高阶统一支持）

见commit 892a6d6从Miles Sabin

-Xexperimental现在只包括-Ypartial-unification

它跟着Paul Chiusano的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 

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