Jakie są ograniczenia wnioskowania typów wyższych typów w Scali?

Question

W poniższym uproszczonym przykładowy kod:

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 

mogę zadzwonić applicativeTwice na applicativeOne oraz rodzaj wnioskowania działa tak szybko, jak próbuję to nazwać na applicativeTwice (applicativeOne), wnioskowanie kończy się niepowodzeniem:

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

błędy w Scala 2.10.0 są

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

dlaczego nie? "F" mecz z niczego (z prawej rodzaju)? Ostatecznie chciałbym aplikativeTwice być niejawna funkcja, ale musiałem najpierw uzyskać wnioskowanie typu pracy. Widziałem podobne pytania, a odpowiedzi wskazywały na ograniczenia w algorytmach wnioskowania typu. Ale ta sprawa wydaje się dość ograniczająca i musi być dość irytująca w transformatorach Monada, więc podejrzewam, że brakuje mi jakiejś sztuczki do obejścia tego.

Answer 1

Udało Ci się uniknąć irytacji: SI-2712. Dla jasności, mam zamiar zminimalizować kod nieco:

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

To pokazuje ten sam błąd typu jak Twoja:

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 
        ^

Najpierw trochę składni i terminologii pewnie już wiedzą:

• W Scali mówimy, że zwykły, nieparametryczny typ danych (taki jak Int) ma rodzaj _. Jest to monomorficzna.
• Base, z drugiej strony, jest sparametryzowany. nie możemy używać go jako typu wartości bez podania typu, który zawiera, więc mówimy, że ma rodzaj _[_]. Jest to ranga-1 polimorficzna: konstruktor typu, który przyjmuje typ.
• Recursive idzie dalej: ma dwa parametry: F[_] i A. Liczba parametrów typu nie ma tutaj znaczenia, ale ich rodzaje to robią. F[_] jest polimorficzny 1 stopnia, więc Recursive jest rangowy 2 polimorficzny: jest to konstruktor typu, który przyjmuje konstruktor typu.
• Nazywamy wszystko rangą 2 lub wyższą wyższym krojem, i tu zaczyna się zabawa.

Scala w ogóle nie ma problemów z typami o wyższym typie. Jest to jedna z kilku kluczowych cech, która odróżnia jego typ systemu od, powiedzmy, języka Java. Ale ma problem z częściową aplikacją parametrów typu, gdy mamy do czynienia z typami wyższego rzędu.

Oto problem: Recursive[F[_], A] ma dwa parametry typu.W kodzie przykładowym ty zrobił „typ lambda” trick częściowo zastosować pierwszy parametr, coś jak:

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

Ten przekonuje kompilator, że jesteś dostarczając coś właściwego rodzaju (_[_]) do Recursive konstruktor. Jeśli Scala miał curry listy parametrów typu, Zdecydowanie wykorzystali że tutaj:

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

Niestety, nie (patrz SI-4719). Tak więc, zgodnie z moją najlepszą wiedzą, najczęstszym sposobem radzenia sobie z tym problemem jest "nieuczciwa sztuczka", z powodu Milesa Sabina. Tutaj jest znacznie uproszczona wersja tego, co pojawia się w 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 
    } 
} 

W nieco ręcznie wavey warunkach, to Unapply konstrukt jest jak „pierwszej klasy typu lambda.” Definiujemy cechę reprezentującą twierdzenie, że jakiś typ FA może zostać rozłożony na konstruktor typu F[_] i typ A. Następnie w jego obiekcie towarzyszącym możemy zdefiniować implikacje, aby zapewnić określone dekompozycje dla typów różnego rodzaju. Zdefiniowałem tutaj tylko ten konkretny, który musimy dopasować, ale możesz napisać inne.

Dzięki tej dodatkowej odrobiny kanalizacji, możemy teraz zrobić to, czego potrzebujemy:

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! Teraz typowanie działa, a to się kompiluje. Jako ćwiczenie, którą proponujemy utworzyć dodatkową klasę:

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

... co nie jest naprawdę różni się od Recursive w żaden znaczący sposób, oczywiście, ale po raz kolejny przełamać typu wnioskowanie. Następnie określ dodatkową instalację hydrauliczną potrzebną do jej naprawy. Powodzenia!

Edit

Pytałeś o mniej uproszczonej wersji, coś świadomi typu zajęć. Pewna modyfikacja jest wymagana, ale mam nadzieję, że widzisz podobieństwo. Po pierwsze, oto nasze zmodernizowane 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 
    } 
} 

Ponownie, jest to completely ripped off from scalaz.Teraz niektóre przykładowy kod używając go:

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

Uwaga (3 lata później, lipiec 2016), scala v2.12.0-M5 jest rozpoczęcie wdrażania SI-2172 (wsparcie dla większej unifikacji zamówienia)

Zobacz commit 892a6d6 z Miles Sabin

Tryb

teraz obejmuje tylko -Ypartial-unification

Jest zgodny z Paul Chiusano jest 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 zawiera

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

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