Qu'est-ce qu'un type supérieur en Scala ?

Question

Vous pouvez trouver les éléments suivants sur le web :

1. Type supérieur == constructeur de type ?

   class AClass[T]{...} // For example, class List[T]

   Certains disent qu'il s'agit d'un type supérieur, parce qu'il s'abstrait des types qui seraient conformes à la définition.

   Types supérieurs sont des types qui prennent d'autres types et construisent un nouveau type.

   Ils sont également connus sous le nom de constructeur de type . (Par exemple, dans Programmation en Scala ).

2. Type supérieur == constructeur de type qui prend le constructeur de type comme paramètre de type ?

   Dans le document Des génériques d'un genre supérieur vous pouvez lire

   ... les types qui s'abstraient des types qui s'abstraient des types ('higher-kinded types') ..."

   ce qui suggère que

   class XClass[M[T]]{...} // or
   
   trait YTrait[N[_]]{...} // e.g. trait Functor[F[_]]

   est un type supérieur.

Dans cette optique, il est donc difficile de faire la distinction entre constructeur de type , type supérieur y constructeur de type qui prend les constructeurs de type comme paramètre de type d'où la question ci-dessus.

Answer 1

Permettez-moi de compenser cette confusion en apportant un peu de désambiguïsation. J'aime utiliser l'analogie avec le niveau de valeur pour expliquer cela, car les gens ont tendance à être plus familiers avec cette notion.

Un constructeur de type est un type que vous pouvez appliquer aux arguments de type pour "construire" un type.

Un constructeur de valeur est une valeur que vous pouvez appliquer aux arguments de valeur pour "construire" une valeur.

Les constructeurs de valeurs sont généralement appelés "fonctions" ou "méthodes". Ces "constructeurs" sont également dits "polymorphes" (car ils peuvent être utilisés pour construire des "choses" de forme variable), ou "abstraits" (car ils font abstraction de ce qui varie entre les différentes instanciations polymorphes).

Dans le contexte de l'abstraction/polymorphisme, le premier ordre fait référence à l'"utilisation unique" de l'abstraction : vous faites l'abstraction d'un type une fois, mais ce type lui-même ne peut pas faire l'abstraction de quoi que ce soit. Les génériques de Java 5 sont de premier ordre.

L'interprétation au premier ordre des caractérisations des abstractions ci-dessus sont :

Un constructeur de type est un type que vous pouvez appliquer à des arguments de type approprié pour "construire" un type approprié.

Un constructeur de valeur est une valeur que vous pouvez appliquer à des arguments de valeur appropriés pour "construire" une valeur appropriée.

Pour souligner qu'aucune abstraction n'est impliquée (je suppose qu'on pourrait appeler cela "ordre zéro", mais je n'ai jamais vu cela utilisé nulle part), comme la valeur 1 ou le type String En général, nous disons que quelque chose est une valeur ou un type "propre".

Une valeur propre est "immédiatement utilisable" dans le sens où elle n'attend pas d'arguments (elle ne fait pas abstraction d'eux). Considérez-les comme des valeurs que vous pouvez facilement imprimer/inspecter (sérialiser une fonction est une tricherie !).

Un type correct est un type qui classifie des valeurs (y compris les constructeurs de valeurs), les constructeurs de types ne classifient aucune valeur (ils doivent d'abord être appliqués aux bons arguments de type pour produire un type correct). Pour instancier un type, il est nécessaire (mais pas suffisant) qu'il soit un type approprié. (Il peut s'agir d'une classe abstraite, ou d'une classe à laquelle vous n'avez pas accès).

"Ordre supérieur" est simplement un terme générique qui signifie l'utilisation répétée du polymorphisme/de l'abstraction. Il signifie la même chose pour les types et les valeurs polymorphes. Concrètement, une abstraction d'ordre supérieur s'abstrait de quelque chose qui s'abstrait de quelque chose. Pour les types, le terme "higher-kinded" est une version spécialisée du terme plus général "higher-order".

Ainsi, la version d'ordre supérieur de notre caractérisation devient :

Un constructeur de type est un type que vous pouvez appliquer aux arguments de type (types propres ou constructeurs de type) pour "construire" un type propre (constructeur).

Un constructeur de valeur est une valeur que vous pouvez appliquer aux arguments de valeur (valeurs propres ou constructeurs de valeur) pour "construire" une valeur propre (constructeur).

Ainsi, "d'ordre supérieur" signifie simplement que lorsque vous dites "abstraire sur X", vous le pensez vraiment ! Le site X qui est abstrait ne perd pas ses propres "droits d'abstraction" : il peut abstraire tout ce qu'il veut. (Au fait, j'utilise ici le verbe "abstraire" pour signifier : laisser de côté quelque chose qui n'est pas essentiel pour la définition d'une valeur ou d'un type, afin qu'il puisse être varié/fourni par l'utilisateur de l'abstraction comme argument).

Voici quelques exemples (inspirés des questions posées par Lutz par courriel) de valeurs et de types propres, de premier ordre et d'ordre supérieur :

                   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]})#λ

Où les classes utilisées ont été définies comme suit :

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

Pour éviter l'indirection par la définition de classes, vous devez exprimer d'une manière ou d'une autre les fonctions de type anonymes, qui ne sont pas exprimables directement en Scala, mais vous pouvez utiliser des types structurels sans trop de surcharge syntaxique (la fonction #λ -Le style est dû à https://stackoverflow.com/users/160378/retronym afaik) :

Dans une hypothétique version future de Scala qui prendrait en charge les fonctions de type anonyme, vous pourriez raccourcir la dernière ligne de l'exemple en :

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

(A titre personnel, je regrette d'avoir jamais parlé de "types supérieurs", ce ne sont que des types après tout ! Quand vous avez absolument besoin de désambiguïser, je suggère de dire des choses comme "paramètre de constructeur de type", "membre de constructeur de type", ou "alias de constructeur de type", pour souligner que vous ne parlez pas seulement de types propres).

ps : Pour compliquer encore les choses, "polymorphe" est ambigu d'une autre manière, puisqu'un type polymorphe signifie parfois un type universellement quantifié, tel que Forall T, T => T qui est un type propre, puisqu'il classifie les valeurs polymorphes (en Scala, cette valeur peut être écrite comme le type structurel {def apply[T](x: T): T = x} )

Answer 2

(Cette réponse est une tentative d'agrémenter la réponse d'Adriaan Moors par quelques informations graphiques et historiques).

Les types de type supérieur font partie de Scala depuis la version 2.5.

• Avant cela Scala, comme Java jusqu'à maintenant, ne permettait pas d'utiliser le constructeur de type ("generics" en Java) pour être utilisés comme paramètre de type à un constructeur de type, par exemple

   trait Monad [M[_]]

  n'était pas possible.

  Dans Scala 2.5, le système de types a été étendu par la possibilité de classer les éléments suivants les types à un niveau supérieur (connu sous le nom de polymorphisme du constructeur de type ). Ces classifications sont connues sous le nom de genres.

  (Image dérivée de Des génériques d'un genre supérieur )

  La conséquence est que le constructeur de type (par exemple List ) pourrait être utilisé comme d'autres types dans la position de paramètre de type des constructeurs de type et donc ils sont devenus des types de première classe depuis Scala 2.5. (Similaire aux fonctions qui sont des valeurs de première classe dans Scala).

  Dans le contexte d'un système de type supportant les types supérieurs, nous pouvons distinguer types appropriés des types comme Int ou List[Int] à partir de types de premier ordre comme List y les types d'un genre supérieur como Functor ou Monad (types qui s'abstraient sur des types qui s'abstraient sur des types).

  De l'autre côté, le système de types de Java ne supporte pas les types et n'a donc pas de types. d'un "type supérieur".

  Il faut donc l'envisager dans le contexte du système des types de soutien.

• Dans le cas de Scala, vous voyez souvent des exemples de constructeur de type comme

   trait Iterable[A, Container[_]]

  avec le titre "Higher kinded types", par exemple en Scala pour les programmeurs génériques, section 4.3

  Ce terme est parfois trompeur, car beaucoup font référence aux Container comme type supérieur et non Iterable mais ce qui est plus précis est,

  l'utilisation de Container comme paramètre de constructeur de type d'un type d'ordre supérieur (higher-order) ici Iterable .

Answer 3

En genre de types ordinaires comme Int y Char dont les instances sont des valeurs, est * . Le type de constructeurs de type unaire comme Maybe es * -> * ; les constructeurs de type binaire comme Either ont ( curry ) genre * -> * -> * et ainsi de suite. Vous pouvez afficher des types tels que Maybe y Either comme des fonctions de type : elles prennent un ou plusieurs types, et retournent un type.

Une fonction est ordre supérieur s'il a un commander supérieur à 1, où l'ordre est (officieusement) la profondeur d'imbrication, vers la gauche, des flèches de fonction :

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

Donc, pour faire court, a supérieur Le type est juste une fonction d'ordre supérieur au niveau du type. dont fait abstraction de les constructeurs de type :

• Commande 0 : Int :: *
• Commande 1 : Maybe :: * -> *
• Commande 2 : Functor :: (* -> *) -> Constraint -higher-kinded : convertit les constructeurs de type unaire en contraintes de classe de type

Answer 4

Je dirais : Un type supérieur fait abstraction de un constructeur de type. Par exemple, considérez

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

Aquí Functor est un "type supérieur" (tel qu'il est utilisé dans l'approche de l Document "Generics of a Higher Kind" (Génériques d'un genre supérieur) ). Il ne s'agit pas d'un constructeur de type concret ("premier ordre") comme List (qui fait abstraction des types propres uniquement). Il s'abstrait de tous les constructeurs de types unaires ("premier ordre") (désignés par le symbole F[_] ).

Ou pour le dire d'une autre manière : En Java, nous avons clairement des constructeurs de type (par ex. List<T> ), mais nous n'avons pas de "types supérieurs", parce que nous ne pouvons pas nous abstraire au-dessus d'eux (par exemple, nous ne pouvons pas écrire la fonction Functor interface définie ci-dessus - du moins pas directement ).

Le terme "polymorphisme d'ordre supérieur (constructeur de type)" est utilisé pour décrire les systèmes qui prennent en charge les "types supérieurs".

Answer 5

Le REPL de Scala fournit :kind qui

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

Par exemple,

scala> trait Foo[A]
trait Foo

scala> trait Bar[F[_]]
trait Bar

scala> :kind -v Foo
Foo's kind is F[A]
* -> *
This is a type constructor: a 1st-order-kinded type.

scala> :kind -v Foo[Int]
Foo[Int]'s kind is A
*
This is a proper type.

scala> :kind -v Bar
Bar's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

scala> :kind -v Bar[Foo]
Bar[Foo]'s kind is A
*
This is a proper type.

---

En :help fournit des définitions claires, je pense donc qu'il vaut la peine de le poster ici dans son intégralité (Scala 2.13.2)

scala> :help kind

:kind [-v] <type>
Displays the kind of a given type.

    -v      Displays verbose info.

"Kind" is a word used to classify types and type constructors
according to their level of abstractness.

Concrete, fully specified types such as `Int` and `Option[Int]`
are called "proper types" and denoted as `A` using Scala
notation, or with the `*` symbol.

    scala> :kind Option[Int]
    Option[Int]'s kind is A

In the above, `Option` is an example of a first-order type
constructor, which is denoted as `F[A]` using Scala notation, or
* -> * using the star notation. `:kind` also includes variance
information in its output, so if we ask for the kind of `Option`,
we actually see `F[+A]`:

    scala> :k -v Option
    Option's kind is F[+A]
    * -(+)-> *
    This is a type constructor: a 1st-order-kinded type.

When you have more complicated types, `:kind` can be used to find
out what you need to pass in.

    scala> trait ~>[-F1[_], +F2[_]] {}
    scala> :kind ~>
    ~>'s kind is X[-F1[A1],+F2[A2]]

This shows that `~>` accepts something of `F[A]` kind, such as
`List` or `Vector`. It's an example of a type constructor that
abstracts over type constructors, also known as a higher-order
type constructor or a higher-kinded type.