在Scala中，对更高种类的类型进行推理有哪些限制? [英] What are the limitations on inference of higher-kinded types in Scala?

问题描述

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

In the following simplified sample code:

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)上调用它，推断就会失败:

I can call applicativeTwice on applicativeOne, and type inference works, as soon as I try to call it on applicativeTwice(applicativeOne), inference fails:

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

scala 2.10.0中的错误是

The errors in scala 2.10.0 are

- 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变形金刚中肯定是个烦人的事，所以我怀疑我缺少一些解决此问题的技巧.

Why wouldn't "?F" match with anything (of the right kind) ? Ultimately I'd like applicativeTwice to be an implicit function, but I'd have to get the type inference working first. I have seen similar questions, and the answers pointed to limitations in the type inference algorithms. But this case seems pretty limitative, and must be quite an annoyance in monad transformers, so I suspect I'm missing some trick to work around this.

推荐答案

您遇到了一个常见的烦恼: SI -2712 .为了清楚起见，我将尽量减少您的代码:

You've hit a common annoyance: SI-2712. For clarity, I'm going to minimize your code a bit:

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

这说明了与您相同的类型错误:

This demonstrates the same type error as yours:

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
                    ^

首先您可能已经知道的一些语法和术语:

First a bit of syntax and terminology you probably already know:

• 在Scala中，我们说普通的，非参数化的数据类型(例如Int)的类型为_.它是单态的.
另一方面，
• Base被参数化.我们不能在没有提供它包含的类型的情况下将其用作值的类型，因此我们说它具有种类_[_].它是 rank-1多态的:采用类型的类型构造函数.
• Recursive走得更远:它有两个参数，F[_]和A.类型参数的数量在这里无关紧要，但种类却很重要. F[_]是等级1多态的，所以Recursive是等级2多态的:这是一个采用类型构造函数的类型构造函数.
• 我们称任何排名第二或以上的东西高种，这就是乐趣的开始.

• In Scala we say that a plain, unparameterized data type (such as Int) has kind _. It's monomorphic.
• Base, on the other hand, is parameterized. we can't use it as the type of a value without providing the type it contains, so we say has kind _[_]. It's rank-1 polymorphic: a type constructor that takes a type.
• Recursive goes further still: it has two parameters, F[_] and A. The number of type parameters don't matter here, but their kinds do. F[_] is rank-1 polymorphic, so Recursive is rank-2 polymorphic: it's a type constructor that takes a type constructor.
• We call anything rank two or above higher-kinded, and this is where the fun starts.

Scala通常不会处理种类繁多的类型.这是将其类型系统与Java区别开的几个关键功能之一.但是在处理类型较高的类型时，确实存在类型参数的部分应用问题.

Scala in general doesn't have trouble with higher-kinded types. This is one of several key features that distinguishes its type system from, say, Java's. But it does have trouble with partial application of type parameters when dealing with higher-kinded types.

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

Here's the problem: Recursive[F[_], A] has two type parameters. In your sample code, you did the "type lambda" trick to partially apply the first parameter, something like:

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

这使编译器确信您正在为Recursive构造函数提供正确的种类(_[_]).如果Scala拥有咖喱类型参数列表，那么我肯定会在这里使用它:

This convinces the compiler that you're providing something of the correct kind (_[_]) to the Recursive constructor. If Scala had curried type parameter lists, I'd definitely have used that here:

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

A，不是(请参阅 SI-4719 ).因此，据我所知，迈尔斯·萨宾(Miles Sabin)认为，处理此问题的最常见方法是未应用的把戏".这是scalaz中显示的内容的简化版本:

Alas, it does not (see SI-4719). So, to the best of my knowledge, the most common way of dealing with this problem is the "unapply trick," due to Miles Sabin. Here is a greatly simplified version of what appears in 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适合的特定选项，但您可以编写其他选项.

In somewhat hand-wavey terms, this Unapply construct is like a "first-class type lambda." We define a trait representing the assertion that some type FA can be decomposed into a type constructor F[_] and a type A. Then in its companion object, we can define implicits to provide specific decompositions for types of various kinds. I've only defined here the specific one that we need to make Recursive fit, but you could write others.

有了这些额外的功能，我们现在可以做我们需要做的事情:

With this extra bit of plumbing, we can now do what we need:

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

Ta-da！现在，类型推断有效，并且可以编译.作为练习，我建议您创建一个附加的类:

Ta-da! Now type inference works, and this compiles. As an exercise, I'd suggest you create an additional class:

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

...当然，在任何有意义的方式上与Recursive并没有真正的不同，但是会再次破坏类型推断.然后定义修复它所需的其他管道.祝你好运！

... which isn't really different from Recursive in any meaningful way, of course, but will again break type inference. Then define the additional plumbing needed to fix it. Good luck!

您要求一个简化的版本，可以识别类型类.需要进行一些修改，但希望您可以看到相似之处.首先，这是我们升级后的Unapply:

You asked for a less simplified version, something aware of type-classes. Some modification is required, but hopefully you can see the similarity. First, here's our upgraded 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剥离.现在使用它的一些示例代码:

Again, this is completely ripped off from scalaz. Now some sample code using it:

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

这篇关于在Scala中，对更高种类的类型进行推理有哪些限制?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！