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