scala - Tipos impredicativos vs. subtipificación antigua simple

haskell functional-programming

Question

Un amigo mío planteó una pregunta aparentemente inofensiva sobre el lenguaje de Scala la semana pasada, que no tuve una buena respuesta: si hay una forma fácil de declarar una colección de cosas que pertenecen a una clase de tipo común. Por supuesto, no existe una noción de primera clase de "clase de tipo" en Scala, por lo que tenemos que pensar en esto en términos de rasgos y límites de contexto (es decir, implícitas).

Concretamente, dado algún rasgo T[_] representa una clase de tipo, y tipos A , B y C , con implicaciones correspondientes en el alcance T[A] , T[B] y T[C] , queremos declarar algo así como una List[T[a] forAll { type a }] , en el que podemos lanzar instancias de A , B y C con total impunidad. Esto, por supuesto, no existe en Scala; una pregunta del año pasado analiza esto con más profundidad.

La pregunta natural de seguimiento es "¿cómo lo hace Haskell?" Bueno, GHC en particular tiene una extensión de sistema de tipo llamada polimorfismo impredicativo , descrito en el documento "Tipos de Boxy" . En resumen, dada una clase de tipo T uno puede construir legalmente una lista [forall a. T a => a] [forall a. T a => a] . Dada una declaración de este formulario, el compilador hace algo de magia de paso de diccionario que nos permite retener las instancias de clase de tipo correspondientes a los tipos de cada valor en la lista en tiempo de ejecución.

La cosa es que la "magia que pasa el diccionario" se parece mucho a "vtables". En un lenguaje orientado a objetos como Scala, la subtipificación es un mecanismo mucho más simple y natural que el enfoque de "Tipos de Boxy". Si nuestra A , B y C extienden el rasgo T , entonces podemos simplemente declarar la List[T] y ser felices. Del mismo modo, como señala Miles en un comentario a continuación, si todos extienden los rasgos T1 , T2 y T3 entonces puedo usar List[T1 with T2 with T3] como equivalente al Haskell impredicativo [forall a. (T1 a, T2 a, T3 a) => a] [forall a. (T1 a, T2 a, T3 a) => a] .

Sin embargo, la desventaja principal y bien conocida de la subtipificación en comparación con las clases de tipos es el acoplamiento estricto: mis tipos A , B y C tienen que tener su comportamiento en T colado. Supongamos que este es un gran obstáculo y no puedo usar la subtipificación. Así que el término medio en Scala es proxenetas ^ H ^ H ^ H ^ H ^ Conversiones de índigo: dadas algunas A => T , B => T y C => T en alcance implícito, puedo poblar una List[T] con mis valores A , B y C ...

... Hasta que queramos la List[T1 with T2 with T3] . En ese momento, incluso si tenemos conversiones implícitas A => T1 , A => T2 y A => T3 , no podemos poner una A en la lista. Podríamos reestructurar nuestras conversiones implícitas para proporcionar literalmente A => T1 with T2 with T3 , pero nunca antes había visto a nadie hacer eso, y parece ser otra forma de acoplamiento estrecho.

De acuerdo, entonces mi pregunta finalmente es, supongo, una combinación de un par de preguntas que se hicieron previamente aquí: "¿por qué evitar subtipar?" y "ventajas del subtipado sobre clases de tipos" ... ¿existe alguna teoría unificadora que diga que el polimorfismo impredicativo y el polimorfismo de subtipo son uno y el mismo? ¿Son las conversiones implícitas de alguna manera el amor secreto de los dos? ¿Y puede alguien articular un patrón bueno y limpio para expresar límites múltiples (como en el último ejemplo anterior) en Scala?

Answer 1

Estás confundiendo tipos impredicativos con tipos existenciales. Los tipos impredicativos le permiten poner valores polimórficos en una estructura de datos, no arbitrarios concretos. En otras palabras [forall a. Num a => a] [forall a. Num a => a] significa que tiene una lista donde cada elemento funciona como cualquier tipo numérico, por lo que no puede poner, por ejemplo, Int y Double en una lista de tipo [forall a. Num a => a] [forall a. Num a => a] , pero puede poner algo como 0 :: Num a => a en él. Los tipos impredicativos no son lo que quieres aquí.

Lo que quieres son tipos existenciales, es decir, [exists a. Num a => a] [exists a. Num a => a] (sintaxis real de Haskell), que dice que cada elemento es un tipo numérico desconocido. Para escribir esto en Haskell, sin embargo, tenemos que introducir un tipo de datos de contenedor:

data SomeNumber = forall a. Num a => SomeNumber a

Tenga en cuenta que el cambio de exists a forall . Eso es porque estamos describiendo el constructor . Podemos poner cualquier tipo numérico, pero luego el sistema de tipo "olvida" qué tipo era. Una vez que lo sacamos de nuevo (por coincidencia de patrones), todo lo que sabemos es que se trata de un tipo numérico. Lo que sucede bajo el capó es que el tipo SomeNumber contiene un campo oculto que almacena el diccionario de clase de tipo (también conocido como vtable / implicit), por lo que necesitamos el tipo de envoltura.

Ahora podemos usar el tipo [SomeNumber] para una lista de números arbitrarios, pero necesitamos ajustar cada número en el camino, por ejemplo [SomeNumber (3.14 :: Double), SomeNumber (42 :: Int)] . El diccionario correcto para cada tipo se busca y se almacena automáticamente en el campo oculto en el punto en que ajustamos cada número.

La combinación de tipos existenciales y clases de tipos es en cierto modo similar a la subtipificación, ya que la principal diferencia entre las clases de tipos y las interfaces es que con las clases de tipos el vtable viaja por separado de los objetos, y los tipos existenciales empacan los objetos y los vtables nuevamente juntos.

Sin embargo, a diferencia de la subtipificación tradicional, no está obligado a emparejarlos uno a uno, por lo que podemos escribir cosas como esta, que empaqueta un vtable con dos valores del mismo tipo.

data TwoNumbers = forall a. Num a => TwoNumbers a a
f :: TwoNumbers -> TwoNumbers
f (TwoNumbers x y) = TwoNumbers (x+y) (x*y)
list1 = map f [TwoNumbers (42 :: Int) 7, TwoNumbers (3.14 :: Double) 9]
-- ==> [TwoNumbers (49 :: Int) 294, TwoNumbers (12.14 :: Double) 28.26]

o incluso cosas más elegantes. Una vez que ajustamos el patrón en el contenedor, volvemos a la tierra de las clases tipo. Aunque no sabemos qué tipo son y , sabemos que son iguales y tenemos el diccionario correcto disponible para realizar operaciones numéricas sobre ellos.

Todo lo anterior funciona de manera similar con múltiples clases de tipos. El compilador simplemente generará campos ocultos en el tipo de envoltura para cada vtable y los traerá todos al alcance cuando coincidamos con el patrón.

data SomeBoundedNumber = forall a. (Bounded a, Num a) => SBN a
g :: SomeBoundedNumber -> SomeBoundedNumber
g (SBN n) = SBN (maxBound - n)
list2 = map g [SBN (42 :: Int32), SBN (42 :: Int64)]
-- ==> [SBN (2147483605 :: Int32), SBN (9223372036854775765 :: Int64)]

Como soy muy principiante en lo que respecta a Scala, no estoy seguro de poder ayudarte con la parte final de tu pregunta, pero espero que al menos haya aclarado algo de la confusión y te haya dado algunas ideas sobre cómo para proceder.

Answer 2

La respuesta de @hammar es perfectamente correcta. Esta es la forma scala de hacerlo. Por ejemplo, tomaré Show como la clase de tipo y los valores i y d para empacar en una lista:

// The type class
trait Show[A] {
def show(a : A) : String
}
// Syntactic sugar for Show
implicit final class ShowOps[A](val self : A)(implicit A : Show[A]) {
def show = A.show(self)
}
implicit val intShow = new Show[Int] {
def show(i : Int) = "Show of int " + i.toString
}
implicit val stringShow = new Show[String] {
def show(s : String) = "Show of String " + s
}
val i : Int = 5
val s : String = "abc"

Lo que queremos es poder ejecutar el siguiente código

val list = List(i, s)
for (e <- list) yield e.show

Crear la lista es fácil, pero la lista no "recordará" el tipo exacto de cada uno de sus elementos. En cambio, reubicará cada elemento a un súper tipo común T El tipo súper super más preciso entre String e Int siendo Any , el tipo de la lista es List[Any] .

El problema es: ¿qué olvidar y qué recordar? Queremos olvidar el tipo exacto de los elementos PERO queremos recordar que todos son instancias de Show . La siguiente clase hace exactamente eso

abstract class Ex[TC[_]] {
type t
val value : t
implicit val instance : TC[t]
}
implicit def ex[TC[_], A](a : A)(implicit A : TC[A]) = new Ex[TC] {
type t = A
val value = a
val instance = A
}

Esta es una codificación de lo existencial:

val ex_i : Ex[Show] = ex[Show, Int](i)
val ex_s : Ex[Show] = ex[Show, String](s)

Empaqueta un valor con la instancia de clase de tipo correspondiente.

Finalmente, podemos agregar una instancia para Ex[Show]

implicit val exShow = new Show[Ex[Show]] {
def show(e : Ex[Show]) : String = {
import e._
e.value.show
}
}

La import e._ es necesaria para poner la instancia en el alcance. Gracias a la magia de las implicidades:

val list = List[Ex[Show]](i , s)
for (e <- list) yield e.show

que está muy cerca del código esperado.