Tipos imprsicativos vs. subtipificación antigua simple

Question

Un amigo mío planteó una pregunta aparentemente inofensiva sobre el lenguaje Scala la semana pasada que no tuve una buena respuesta a: si hay una forma fácil de declarar una colección de elementos pertenecientes a alguna clase de tipo común . Por supuesto, no existe una noción de primera clase de "tipo de letra" 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[_] que representa una clase de tipos y tipos A, B y C, la implícitos correspondientes en su alcance T[A], T[B] y T[C], queremos declarar algo así como un List[T[a] forAll { type a }], en la que podemos lanzar instancias de A , B y C con impunidad. Esto, por supuesto, no existe en Scala; a question last year analiza esto con más profundidad.

La siguiente pregunta natural es "¿Cómo lo hace Haskell?" Bueno, GHC en particular tiene una extensión de sistema tipo llamada impredicative polymorphism, descrita en el documento "Boxy Types". En resumen, dada una clase de tipos T, uno puede construir legalmente una lista [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 "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 nuestro A, B y C extienden el rasgo T, entonces simplemente podemos declarar List[T] y ser felices. Del mismo modo, como señala Miles en un comentario a continuación, si todos amplían los rasgos T1, T2 y T3, entonces puedo usar List[T1 with T2 with T3] como equivalente al imprevisible Haskell [forall a. (T1 a, T2 a, T3 a) => a].

Sin embargo, la principal desventaja, conocido con subtipos en comparación con las clases de tipos es estrecho acoplamiento: mis A, B y C tipos tienen que tener su comportamiento T cuece en Asumamos que este es un motivo de ruptura importante, y yo puede. 't use subtipificación. Por lo que el término medio en Scala es proxenetas^conversiones H^H^H^H^Himplicit: dado algunos A => T, B => T y C => T alcance implícita, lo que puedo de nuevo felizmente llenar un List[T] con mis A, B y valores C ...

... Hasta que queramos 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 un 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 ajustado.

bien, así que mi pregunta es, finalmente, supongo, una combinación de un par de preguntas que antes se le preguntó aquí: "why avoid subtyping?" y "advantages of subtyping over typeclasses" ... ¿hay alguna teoría unificadora que dice que el polimorfismo impredicativo y el polimorfismo subtipo son una y la misma ? ¿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á confundiendo tipos impredicativos con tipos existenciales.Los tipos impredicativos le permiten poner valores polimórficos en una estructura de datos, no arbitrarios. En otras palabras, [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, p. Ej. Int y Double en una lista del tipo [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 quiere son tipos existenciales, es decir, [exists a. Num a => a] (sin sintaxis real de Haskell), que dice que cada elemento es de un tipo numérico desconocido. Para escribir esto en Haskell, sin embargo, tenemos que introducir un envoltorio tipo de datos:

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

nota el cambio de exists a forall. Eso es porque estamos describiendo el constructor . Podemos poner cualquier tipo numérico en, pero luego el sistema de tipos "olvida" de 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 obtener una lista de números arbitrarios, pero tenemos que ajustar cada número al entrar, p. Ej. [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 de alguna manera similar a los subtipos, ya que la principal diferencia entre el tipo clases e interfaces es que con el tipo clases la viable viaja por separado de los objetos, y los tipos existenciales paquetes de objetos y vtables vuelta juntos de nuevo.

Sin embargo, a diferencia de la subtipificación tradicional, no está obligado a vincularlos 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 x y y, sabemos que son iguales y tenemos el diccionario correcto disponible para realizar operaciones numéricas en ellos.

Todo lo anterior funciona de manera similar con varias 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 estoy en gran medida un principiante cuando se trata de la Scala, no estoy seguro de que puedo ayudar con la parte final de su pregunta, pero espero que esto al menos se ha aclarado algunas de las confusiones y te di algunas ideas sobre cómo proceder.

Answer 2

La respuesta de @ hammar está perfectamente en lo cierto. Esta es la forma scala de hacerlo.Para el ejemplo voy a 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 

construcción 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 super tipo común T. El tipo súper súper más preciso entre String y Int es 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 casos de Show. La siguiente clase hace exactamente que

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 la existencial:

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

Se paquete de un valor con la instancia de la clase tipo correspondiente.

Por último podemos añadir una instancia para Ex[Show]

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

El import e._ que se requiere para llevar el caso a su alcance. Gracias a la magia de implicits:

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

que es muy similar al código esperado.