generics - ¿Qué es un tipo de tipo superior en Scala?

types constructor (4)

(Esta respuesta es un intento de decorar la respuesta de los moros de Adriaan con información gráfica e histórica).

Los tipos más cariñosos son parte de Scala desde 2.5.

Antes de eso, Scala, como Java hasta ahora, no permitía usar el constructor de tipo ("genéricos" en Java) para ser usado como parámetro de tipo para un constructor de tipo. p.ej
trait Monad [M[_]]
no era posible
En Scala 2.5, el sistema de tipos se había extendido por la capacidad de clasificar los tipos en un nivel superior (conocido como polimorfismo constructor de tipos ). Estas clasificaciones son conocidas como clases.
(Imagen derivada de genéricos de una clase superior )
La consecuencia es que el constructor de tipos (por ejemplo, la List ) podría usarse igual que otros tipos en la posición de parámetros de tipo de los constructores de tipos, por lo que se convirtieron en tipos de primera clase desde Scala 2.5. (Similar a las funciones que son valores de primera clase en Scala).
En el contexto de un sistema de tipos que admite tipos superiores, podemos distinguir tipos adecuados , tipos como Int o List[Int] de tipos de primer orden como List y tipos de un tipo superior como Functor o Monad (tipos que se abstraen sobre tipos que se resumen) sobre tipos).
El sistema de tipos de Java en el otro lado no admite tipos y, por lo tanto, no tiene tipos de "tipo superior".
Por lo tanto, esto debe verse en el contexto del sistema de tipos de soporte.
En el caso de Scala, a menudo se ven ejemplos de un constructor de tipos como
trait Iterable[A, Container[_]]
con el título "Tipos de tipo más alto", por ejemplo, en Scala para programadores genéricos, sección 4.3
Esto a veces es erróneo, porque muchos se refieren a Container como un tipo de tipo más alto y no Iterable , pero lo que es más preciso es,
el uso de Container como tipo de parámetro de constructor de un tipo ordenado más alto (orden superior) aquí es Iterable .

Puedes encontrar lo siguiente en la web:

Tipo de tipo más alto == constructor de tipo?
class AClass[T]{...} // For example, class List[T]
Algunos dicen que este es un tipo de tipo superior, porque se abstrae sobre tipos que serían compatibles con la definición.
Los tipos ordenados más altos son tipos que toman otros tipos y construyen un nuevo tipo
Estos, sin embargo, también se conocen como constructor de tipo . (Por ejemplo, en Programación en Scala ).
Tipo más alto tipo = = constructor de tipo que toma el constructor de tipo como un parámetro de tipo?
En los genéricos de papel de un tipo superior , puedes leer
... tipos que se abstraen sobre tipos que se abstraen sobre tipos (''tipos de tipo superior'') ... "
lo que sugiere que
class XClass[M[T]]{...} // or trait YTrait[N[_]]{...} // e.g. trait Functor[F[_]]
Es un tipo de tipo superior.

Por lo tanto, teniendo esto en cuenta, es difícil distinguir entre constructor de tipo , tipo de tipo superior y constructor de tipo que toma a los constructores de tipo como parámetro de tipo , por lo tanto, la pregunta anterior.

El kind de tipos ordinarios como Int y Char , cuyas instancias son valores, es * . El tipo de constructores de tipo unario como Maybe es * -> * ; los constructores de tipo binario como Either tienen tipo (al curried ) * -> * -> * , y así sucesivamente. Puede ver tipos como Maybe y Either como funciones de nivel de tipo: toman uno o más tipos y devuelven un tipo.

Una función es de orden superior si tiene un orden mayor que 1, donde el orden es (informalmente) la profundidad de anidamiento, a la izquierda, de las flechas de función:

Orden 0: 1 :: Int
Orden 1: chr :: Int -> Char
Orden 2: fix :: (a -> a) -> a , map :: (a -> b) -> [a] -> [b]
Orden 3: ((A -> B) -> C) -> D
Orden 4: (((A -> B) -> C) -> D) -> E

Por lo tanto, para resumir, un tipo de orden superior es solo una función de orden superior de nivel de tipo.

Orden 0: Int :: *
Orden 1: Maybe :: * -> *
Orden 2: Functor :: (* -> *) -> Constraint —mayas ordenado: convierte constructores de tipo unario en restricciones de clase de tipos

Permítame compensar por comenzar algo de esta confusión lanzando algo de desambiguación. Me gusta usar la analogía con el nivel de valor para explicar esto, ya que las personas tienden a estar más familiarizadas con él.

Un constructor de tipo es un tipo que puede aplicar a los argumentos de tipo para "construir" un tipo.
Un constructor de valores es un valor que puede aplicar a los argumentos de valor para "construir" un valor.

Los constructores de valor suelen denominarse "funciones" o "métodos". También se dice que estos "constructores" son "polimórficos" (porque se pueden usar para construir "cosas" de "formas" variables), o "abstracciones" (ya que se abstienen de lo que varía entre diferentes instancias polimórficas).

En el contexto de la abstracción / polimorfismo, el primer orden se refiere al "uso único" de la abstracción: se abstrae sobre un tipo una vez, pero ese tipo en sí no puede abstraerse sobre nada. Los genéricos de Java 5 son de primer orden.

La interpretación de primer orden de las caracterizaciones anteriores de abstracciones es:

Un constructor de tipo es un tipo que puede aplicar a los argumentos de tipo adecuado para "construir" un tipo adecuado.
Un constructor de valores es un valor que puede aplicar a los argumentos de valores adecuados para "construir" un valor adecuado.

Para enfatizar que no hay abstracción involucrada (supongo que podría llamarse "orden cero", pero no he visto esto usado en ninguna parte), como el valor 1 o el tipo String , generalmente decimos que algo es un valor "correcto" o tipo.

Un valor apropiado es "inmediatamente utilizable" en el sentido de que no está esperando argumentos (no se abstrae sobre ellos). Piense en ellos como valores que puede imprimir / inspeccionar fácilmente (¡serializar una función es un engaño!).

Un tipo adecuado es un tipo que clasifica los valores (incluidos los constructores de valores), los constructores de tipos no clasifican ningún valor (primero deben aplicarse a los argumentos de tipo correctos para obtener un tipo adecuado). Para crear una instancia de un tipo, es necesario (pero no suficiente) que sea un tipo adecuado. (Puede ser una clase abstracta o una clase a la que no tiene acceso).

"Orden superior" es simplemente un término genérico que significa uso repetido de polimorfismo / abstracción. Significa lo mismo para tipos y valores polimórficos. Concretamente, una abstracción de orden superior se abstrae sobre algo que se abstrae sobre algo. Para los tipos, el término "clase superior" es una versión de propósito especial de la más general "orden superior".

Así, la versión de orden superior de nuestra caracterización se convierte en:

Un constructor de tipo es un tipo que puede aplicar a los argumentos de tipo (tipos adecuados o constructores de tipo) para "construir" un tipo adecuado (constructor).
Un constructor de valores es un valor que puede aplicar a los argumentos de valor (valores adecuados o constructores de valores) para "construir" un valor adecuado (constructor).

Por lo tanto, "orden superior" simplemente significa que cuando dices "abstraerse sobre X", ¡lo dices de verdad! La X que se abstrae no pierde sus propios "derechos de abstracción": puede abstraer todo lo que quiera. (Por cierto, uso el verbo "abstracto" aquí para significar: omitir algo que no es esencial para la definición de un valor o tipo, para que el usuario de la abstracción pueda variarlo / proporcionarlo como argumento .)

Aquí hay algunos ejemplos (inspirados por las preguntas de Lutz por correo electrónico) de tipos y valores correctos, de primer orden y de orden superior:

proper first-order higher-order values 10 (x: Int) => x (f: (Int => Int)) => f(10) types (classes) String List Functor types String ({type λ[x] = x})#λ ({type λ[F[x]] = F[String]})#λ

Donde las clases utilizadas fueron definidas como:

class String class List[T] class Functor[F[_]]

Para evitar el direccionamiento indirecto a través de la definición de clases, debe expresar de algún modo funciones de tipo anónimo, que no se pueden expresar directamente en Scala, pero puede usar tipos estructurales sin demasiada sobrecarga sintáctica (el estilo #λ se debe a https://.com/users/160378/retronym afaik):

En alguna versión futura hipotética de Scala que admite funciones de tipo anónimo, podría acortar esa última línea de los ejemplos a:

types (informally) String [x] => x [F[x]] => F[String]) // I repeat, this is not valid Scala, and might never be

(En una nota personal, me arrepiento de haber hablado de "tipos de clase superior", después de todo, ¡son tipos! Cuando es absolutamente necesario desconcertar, sugiero que digan cosas como "tipo de parámetro de constructor", "miembro de tipo constructor" , o "alias de constructor de tipo", para enfatizar que no está hablando solo de los tipos adecuados.)

ps: Para complicar aún más las cosas, "polimórfico" es ambiguo de una manera diferente, ya que un tipo polimórfico a veces significa un tipo cuantificado universalmente, como Forall T, T => T , que es un tipo adecuado, ya que clasifica los valores polimórficos ( en Scala, este valor puede escribirse como el tipo estructural {def apply[T](x: T): T = x} )

Yo diría: Un tipo de tipo superior se abstrae sobre un constructor de tipo. Por ejemplo, considerar

trait Functor [F[_]] { def map[A,B] (fn: A=>B)(fa: F[A]): F[B] }

Aquí Functor es un "tipo de tipo superior" (tal como se utiliza en el documento "Genéricos de un tipo más alto"). No es un constructor de tipo concreto ("de primer orden") como List (que se abstrae solo sobre los tipos adecuados). Se abstrae sobre todos los constructores de tipo unario ("de primer orden") (como se denota con F[_] ).

O para decirlo de otra manera: en Java, tenemos claramente constructores de tipos (por ejemplo, List<T> ), pero no tenemos "tipos de tipos más altos", porque no podemos abstraerlos (por ejemplo, no podemos escribir el Interfaz funcional definida anteriormente (al menos no directly ).

El término "polimorfismo de orden superior (constructor de tipo)" se utiliza para describir sistemas que admiten "tipos de tipo más alto".