Những hạn chế về suy luận của các loại cao cấp trong Scala là gì?

Question

Trong đoạn mã sau đơn giản hóa mẫu:

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 

tôi có thể gọi applicativeTwice trên applicativeOne, và suy luận kiểu hoạt động, ngay sau khi tôi cố gắng gọi nó trên applicativeTwice (applicativeOne), suy luận không:

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

những sai sót trong scala 2.10.0 là

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

tại sao không "? F" phù hợp với bất cứ điều gì (thuộc loại phải)? Cuối cùng tôi muốn applicativeTwice là một hàm ẩn, nhưng tôi phải có suy luận kiểu làm việc đầu tiên. Tôi đã thấy các câu hỏi tương tự và câu trả lời chỉ ra các hạn chế trong các thuật toán suy luận loại. Nhưng trường hợp này có vẻ khá hạn chế, và phải khá là phiền toái trong các máy biến áp đơn nguyên, vì vậy tôi nghi ngờ tôi đang thiếu một số thủ thuật để giải quyết vấn đề này.

Answer 1

Bạn đã gặp phải một sự khó chịu chung: SI-2712. Để rõ ràng, tôi sẽ hạn chế tối đa mã của bạn một chút:

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

này cho thấy lỗi tương tự kiểu như của bạn:

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 
        ^

Lần đầu tiên một chút cú pháp và thuật ngữ có thể bạn đã biết:

• Trong Scala, chúng tôi nói rằng một loại dữ liệu đơn giản, không được tham số (chẳng hạn như Int) có loại _. Đó là monomorphic. Mặt khác, tham số
• Base được tham số hóa. chúng tôi không thể sử dụng nó làm loại giá trị mà không cung cấp loại giá trị chứa, vì vậy chúng tôi nói có loại _[_]. Đó là xếp hạng-1 đa hình: một trình tạo kiểu có kiểu.
• Recursive tiếp tục hoạt động: có hai tham số, F[_] và A. Số lượng các tham số kiểu không quan trọng ở đây, nhưng các kiểu của chúng thì có. F[_] là xếp hạng-1 đa hình, vì vậy Recursive là xếp hạng-2 đa hình: đó là một hàm tạo kiểu có một hàm tạo kiểu.
• Chúng tôi gọi bất kỳ thứ gì xếp hạng hai hoặc cao hơn loại cao hơn và đây là nơi bắt đầu vui vẻ.

Scala nói chung không gặp sự cố với các loại cao cấp hơn. Đây là một trong một số tính năng chính phân biệt hệ thống kiểu của nó từ, ví dụ, của Java. Nhưng nó có vấn đề với một phần ứng dụng của các thông số loại khi giao dịch với các loại cao cấp hơn.

Đây là vấn đề: Recursive[F[_], A] có hai thông số loại.Trong mã mẫu của bạn, bạn đã làm các "loại lambda" lừa một phần áp dụng các tham số đầu tiên, một cái gì đó như:

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

này thuyết phục các trình biên dịch mà bạn đang cung cấp một cái gì đó thuộc loại chính xác (_[_]) đến Recursive constructor. Nếu Scala đã cà ri danh sách tham số kiểu, tôi muốn chắc chắn rằng đã sử dụng ở đây:

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

Alas, nó không (xem SI-4719). Vì vậy, theo hiểu biết tốt nhất của tôi, cách phổ biến nhất để đối phó với vấn đề này là "lừa không khéo léo", do Miles Sabin. Dưới đây là một phiên bản đơn giản hóa rất nhiều về những gì xuất hiện trong 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 
    } 
} 

Về phần tay Xù, Unapply cấu trúc này giống như một "loại lambda hạng nhất." Chúng tôi xác định một đặc điểm đại diện cho xác nhận rằng một số loại FA có thể được phân tách thành một hàm tạo kiểu F[_] và một loại A. Sau đó, trong đối tượng đồng hành của nó, chúng ta có thể xác định implicits để cung cấp các phân tách cụ thể cho các loại khác nhau. Tôi đã chỉ xác định ở đây một cụ thể mà chúng ta cần phải làm cho phù hợp với Recursive, nhưng bạn có thể viết những người khác.

Với chút thêm này của hệ thống ống nước, bây giờ chúng ta có thể làm những gì chúng ta cần:

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! Bây giờ gõ suy luận hoạt động, và điều này biên dịch. Là một tập thể dục, tôi muốn đề nghị bạn tạo một lớp bổ sung:

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

... mà không phải là thực sự khác biệt so với Recursive trong bất kỳ cách có ý nghĩa, tất nhiên, nhưng một lần nữa sẽ phá vỡ kiểu suy luận. Sau đó, xác định đường ống bổ sung cần thiết để sửa chữa nó. Chúc may mắn!

Chỉnh sửa

Bạn đã yêu cầu phiên bản ít đơn giản hơn, nhận thức về loại lớp học. Một số sửa đổi là cần thiết, nhưng hy vọng bạn có thể thấy sự giống nhau. Thứ nhất, đây là nâng cấp của chúng tôi 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 
    } 
} 

Một lần nữa, đây là completely ripped off from scalaz.Bây giờ một số mẫu mã sử dụng nó:

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

Note (3 năm sau đó, tháng 7 năm 2016), scala v2.12.0-M5 đang bắt đầu triển khai SI-2172 (hỗ trợ thống nhất bậc cao)

Xem commit 892a6d6 từ Miles Sabin

Chế độ -Xexperimental hiện chỉ bao gồm -Ypartial-unification

Nó theo sau Paul Chiusano 's 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 

Các test/files/neg/t2712-1.scala bao gồm:

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

Và (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 
}