Каковы ограничения на вывод типов с более высоким родом в 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

Я могу вызвать ApplicativeTwice для ApplicativeOne, и вывод типа работает, как только я пытаюсь вызвать его для 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 был неявной функцией, но сначала мне нужно было бы сделать вывод типа работающим. Я видел похожие вопросы, и ответы указывали на ограничения в алгоритмах вывода типов. Но этот случай кажется довольно ограничительным и, должно быть, раздражает монадные трансформаторы, поэтому я подозреваю, что мне не хватает хитрости, чтобы обойти это.

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 с другой стороны, параметризован. мы не можем использовать его как тип значения без указания типа, который он содержит, поэтому мы говорим, что имеет вид _[_], Это полиморфный ранг 1: конструктор типа, который принимает тип.
• Recursive идет еще дальше: у него есть два параметра, F[_] а также A, Количество параметров типа здесь не имеет значения, но их типы имеют значение. F[_] является полиморфным ранга 1, так Recursive полиморфна ранга 2: это конструктор типов, который принимает конструктор типов.
• Мы называем что-то на два уровня выше или выше, и здесь начинается самое интересное.

У Скалы вообще нет проблем с типами с более высоким родом. Это одна из нескольких ключевых особенностей, которая отличает систему типов, скажем, от Java. Но у него есть проблемы с частичным применением параметров типов при работе с типами с более высоким родом.

Вот проблема: Recursive[F[_], A] имеет два типа параметров. В своем примере кода вы применили трюк "type lambda", чтобы частично применить первый параметр, например:

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

Это убеждает компилятор, что вы предоставляете что-то правильное (_[_]) к Recursive конструктор. Если бы у Scala были списки параметров типа curry, я бы определенно использовал это здесь:

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). Итак, насколько мне известно, наиболее распространенный способ решения этой проблемы - это "неиспользуемый трюк" из-за Майлза Сабина. Вот очень упрощенная версия того, что появляется в 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
    }
}

Опять же, это полностью оторвано от скалаза. Теперь пример кода с его использованием:

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 г.), scala v2.12.0-M5 начинает внедрять SI-2172 (поддержка объединения более высокого порядка)

Смотрите коммит 892a6d6 от Майлза Сабина

-Xexperimental режим теперь включает только -Ypartial-unification

Это следует простому алгоритму Пола Кьюзано:

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