¿Cuáles son las limitaciones en la inferencia de tipos de clase superior en Scala?

type-inference higher-kinded-types

Question

En el siguiente código de ejemplo simplificado:

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

Puedo llamar dos veces aplicativas en aplicativo, y la inferencia de tipos funciona, tan pronto como intento llamarlo en dos veces aplicativas (aplicativo una), la inferencia falla:

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

Los errores en Scala 2.10.0 son.

- 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]

¿Por qué "? F" no coincide con nada (del tipo correcto)? En última instancia, me gustaría que la dos veces aplicativa fuera una función implícita, pero primero tendría que hacer que la inferencia de tipos funcionara. He visto preguntas similares, y las respuestas apuntan a limitaciones en los algoritmos de inferencia de tipos. Pero este caso parece bastante limitativo, y debe ser bastante molesto en los transformadores de mónada, así que sospecho que me estoy perdiendo algún truco para solucionar esto.

Answer 1

Has golpeado una molestia común: SI-2712 . Para mayor claridad, voy a minimizar un poco tu código:

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

Esto demuestra el mismo tipo de error que el tuyo:

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
                    ^

Primero, un poco de sintaxis y terminología que probablemente ya conozcas:

• En Scala, decimos que un tipo de datos simple y sin parámetros (como Int ) tiene el tipo _ . Es monomorfo .
• Base , por otro lado, está parametrizada. no podemos usarlo como el tipo de un valor sin proporcionar el tipo que contiene, por lo que decimos que tiene el tipo _[_] . Es rango-1 polimórfico : un constructor de tipos que toma un tipo.
• Recursive va aún más lejos: tiene dos parámetros, F[_] y A El número de parámetros de tipo no importa aquí, pero sí lo hacen sus tipos. F[_] es polimórfico de rango 1, por lo que Recursive es polimórfico de rango 2 : es un constructor de tipos que toma un constructor de tipos.
• Llamamos a cualquier rango dos o más alto , y aquí es donde comienza la diversión.

Scala en general no tiene problemas con los tipos de clase superior. Esta es una de varias características clave que distingue su sistema de tipos, por ejemplo, de Java. Pero sí tiene problemas con la aplicación parcial de parámetros de tipo cuando se trata de tipos de tipo superior.

Aquí está el problema: Recursive[F[_], A] tiene dos parámetros de tipo. En su código de muestra, hizo el truco "escriba lambda" para aplicar parcialmente el primer parámetro, algo así como:

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

Esto convence al compilador de que está proporcionando algo del tipo correcto ( _[_] ) al constructor Recursive . Si Scala tuviera listas de parámetros de tipo al curry, definitivamente lo habría usado aquí:

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

Por desgracia, no lo hace (ver SI-4719 ). Por lo que sé, la forma más común de resolver este problema es el "truco de no aplicar", debido a Miles Sabin. Aquí hay una versión enormemente simplificada de lo que aparece en 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
  }
}

En términos un tanto manuales, esta construcción Unapply es como un "tipo lambda de primera clase". Definimos un rasgo que representa la afirmación de que algún tipo FA se puede descomponer en un constructor de tipo F[_] y un tipo A Luego, en su objeto compañero, podemos definir implícitos para proporcionar descomposiciones específicas para tipos de varios tipos. Solo he definido aquí el específico que necesitamos para hacer un ajuste Recursive , pero podrías escribir otros.

Con este bit extra de plomería, ahora podemos hacer lo que necesitamos:

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! Ahora escribe inferencia funciona, y esto se compila. Como ejercicio, te sugiero que crees una clase adicional:

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

... que no es realmente diferente de Recursive de ninguna manera significativa, por supuesto, pero volverá a interrumpir la inferencia de tipos. Luego defina la plomería adicional necesaria para repararlo. ¡Buena suerte!

Editar

Usted solicitó una versión menos simplificada, algo consciente de las clases de tipo. Se requiere alguna modificación, pero espero que pueda ver la similitud. Primero, aquí está nuestro Unapply actualizado:

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

Una vez más, esto es completamente arrancado de Scalaz . Ahora un código de ejemplo usándolo:

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

Nota (3 años después, julio de 2016), scala v2.12.0-M5 está comenzando a implementar SI-2712 (soporte para la unificación de orden superior)

Ver commit 892a6d6 de Miles Sabin

-Xexperimental modo -Xexperimental ahora solo incluye -Ypartial-unification

Sigue el sencillo algoritmo de Paul Chiusano :

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

La test/files/neg/t2712-1.scala incluye:

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

Y ( 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
}