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

275

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

  1. Constructeur de type supérieur == type?

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

    Certains disent qu'il s'agit d'un type de type supérieur, car il résume les types qui seraient conformes à la définition.

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

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

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

    Dans l'article Génériques d'un type supérieur , vous pouvez lire

    ... types qui s'abstiennent sur des types qui s'abstiennent sur des types ("types de type supérieur") ... "

    ce qui suggère que

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

    est un type de type supérieur.

Donc, avec cela à l'esprit, il est difficile de distinguer le constructeur de type , le type de type supérieur et le constructeur de type qui prend les constructeurs de type comme paramètre de type , donc la question ci-dessus.

Lutz
la source
Ajout du Functor de Landei comme exemple.
Lutz

Réponses:

284

Permettez-moi de compenser le début d'une partie de cette confusion en insistant avec une certaine ambiguïté. J'aime utiliser l'analogie avec le niveau de valeur pour expliquer cela, car les gens ont tendance à être plus familiers avec cela.

Un constructeur de type est un type que vous pouvez appliquer à des arguments de type pour «construire» un type.

Un constructeur de valeur est une valeur que vous pouvez appliquer à des 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 "trucs" de "forme" variable), ou des "abstractions" (puisqu'ils s'abstiennent sur ce qui varie entre différentes instanciations polymorphes).

Dans le contexte de l'abstraction / polymorphisme, le premier ordre se réfère à une «utilisation unique» de l'abstraction: vous abstenez sur un type une fois, mais ce type lui-même ne peut pas abstraire sur quoi que ce soit. Les génériques Java 5 sont de premier ordre.

L'interprétation de premier ordre des caractérisations ci-dessus des abstractions est:

Un constructeur de type est un type que vous pouvez appliquer aux arguments de type appropriés 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'il n'y a pas d'abstraction impliquée (je suppose que vous pourriez appeler cela "ordre zéro", mais je n'ai vu cela utilisé nulle part), comme la valeur 1ou le type String, nous disons généralement que quelque chose est une valeur ou un type "correct".

Une valeur appropriée est "immédiatement utilisable" dans le sens où elle n'attend pas d'arguments (elle ne les résume pas). Considérez-les comme des valeurs que vous pouvez facilement imprimer / inspecter (sérialiser une fonction, c'est tricher!).

Un type approprié est un type qui classe les valeurs (y compris les constructeurs de valeurs), les constructeurs de types ne classent aucune valeur (ils doivent d'abord être appliqués aux bons arguments de type pour produire un type approprié). Pour instancier un type, il est nécessaire (mais pas suffisant) que ce soit un type correct. (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 de polymorphisme / abstraction. Cela signifie la même chose pour les types et les valeurs polymorphes. Concrètement, une abstraction d'ordre supérieur s'abstrait sur quelque chose qui s'abstrait sur quelque chose. Pour les types, le terme "de type supérieur" est une version spéciale de "l'ordre supérieur" plus général.

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 appropriés ou constructeurs de type) pour "construire" un type approprié (constructeur).

Un constructeur de valeur est une valeur que vous pouvez appliquer à des arguments de valeur (valeurs appropriées ou constructeurs de valeur) pour "construire" une valeur appropriée (constructeur).

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

Voici quelques exemples (inspirés des questions de Lutz par e-mail) de valeurs et de types appropriés, 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:

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

Pour éviter l'indirection en définissant des classes, vous devez en quelque sorte exprimer des fonctions de type anonyme, qui ne sont pas directement exprimables dans Scala, mais vous pouvez utiliser des types structurels sans trop de surcharge syntaxique (le style est dû à https://stackoverflow.com / utilisateurs / 160378 / retronym afaik):

Dans une future version hypothétique de Scala qui prend en charge les fonctions de type anonyme, vous pouvez raccourcir cette dernière ligne des exemples pour:

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

(Sur une note personnelle, je regrette de n'avoir jamais parlé de "types de type supérieur", ce ne sont que des types! Quand vous avez absolument besoin de lever les ambiguïtés, je suggère de dire des choses comme "type constructeur paramètre", "type constructeur membre" , ou "type constructor alias", pour souligner que vous ne parlez pas uniquement des types appropriés.)

ps: Pour compliquer davantage les choses, "polymorphe" est ambigu d'une manière différente, car un type polymorphe signifie parfois un type universellement quantifié, tel que Forall T, T => T, qui est un type approprié, car il classe les valeurs polymorphes (dans Scala, cette valeur peut être écrit comme le type structurel {def apply[T](x: T): T = x})

Adriaan Moors
la source
1
voir aussi: adriaanm.github.com/research/2010/10/06/…
Adriaan Moors
5
L'article d'Adriaan "Type Constructor Polymorphism" maintenant sur adriaanm.github.com/research/2010/10/06/…
Steven Shaw
Je continue à le lire comme un parent plus élevé et à imaginer un esprit de parenté
Janac Meena
110

(Cette réponse est une tentative de décorer la réponse d'Adriaan Moors par des informations graphiques et historiques.)

Les types plus élevés font partie de Scala depuis la 2.5.

  • Avant cela, Scala, en tant que Java jusqu'à présent, ne permettait pas d'utiliser le constructeur de type ("génériques" en Java) pour être utilisé comme paramètre de type pour un constructeur de type. par exemple

     trait Monad [M[_]]

    n'était pas possible.

    Dans Scala 2.5, le système de types avait été étendu par la possibilité de classer les types à un niveau supérieur (connu sous le nom de polymorphisme de constructeur de type ). Ces classifications sont appelées sortes.

    Type et type de realtion, ** dérivé ** de "Generics of a Higher Kind" (Image dérivée de génériques d'un type supérieur )

    La conséquence est que ce constructeur de type (par exemple List) pourrait être utilisé comme les autres types dans la position des paramètres 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 types supportant des types supérieurs, nous pouvons distinguer les types appropriés , les types comme Intou les types List[Int]de premier ordre comme Listet les types de type supérieur comme Functorou Monad(types qui s'abstiennent sur les types qui s'abstiennent sur les types).

    Le système de types de Java, d'autre part, ne prend pas en charge les types et n'a donc aucun type de "type supérieur".

    Il faut donc voir cela dans le contexte du système de type de support.

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

     trait Iterable[A, Container[_]]

    avec le titre "Types supérieurs", par exemple dans Scala pour les programmeurs génériques, section 4.3

    Ceci est missleading parfois, parce que beaucoup se réfèrent à Containercomme type supérieur kinded et non Iterable, mais ce qui est est plus précis,

    l'utilisation ici du Containerparamètre constructeur de type d'un type de type supérieur (d'ordre supérieur) Iterable.

Lutz
la source
80

Le type de types ordinaires comme Intet Char, dont les instances sont des valeurs, est *. Le genre de constructeurs de type unaire comme Maybeest * -> *; les constructeurs de type binaire comme Eitherhave ( curried ) kind * -> * -> *, et ainsi de suite. Vous pouvez afficher les types comme Maybeet en Eithertant que fonctions au niveau du type: ils prennent un ou plusieurs types et renvoient un type.

Une fonction est d'ordre supérieur si elle a un ordre supérieur à 1, où l'ordre est (informellement) la profondeur d'imbrication, à gauche, des flèches de fonction:

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

Donc, pour faire court, un type de type supérieur n'est qu'une fonction d'ordre supérieur au niveau du type.

  • Ordre 0: Int :: *
  • Ordre 1: Maybe :: * -> *
  • Ordre 2: Functor :: (* -> *) -> Constraint—de type supérieur: convertit les constructeurs de type unaire en contraintes de classe de types
Jon Purdy
la source
Ok je l'ai compris, quels seraient alors des exemples dans Scala pour (* ⇒ *) ⇒ * et (* ⇒ *) ⇒ (* ⇒ *)? Le Functor de Landei rentrerait-il dans la première catégorie ou plutôt dans la seconde?
Lutz
1
@lutz: Ce serait dans la première catégorie: Functorproduit un type approprié (enfin, trait, mais même idée) à Functor[F[_]]partir d'un constructeur de type F.
Jon Purdy
1
@Jon: Un post très perspicace, merci. Le convertisseur de type (* => *) => (* => *)peut-il être exprimé en Scala? Sinon, dans une autre langue?
Eugen Labun
@JonPurdy La comparaison entre le * ⇒ * ⇒ *curry est très utile. Merci!
Lifu Huang du
(* ⇒ *) ⇒ (* ⇒ *)peut également être orthographié (* ⇒ *) ⇒ * ⇒ *. Il peut être exprimé en Scala comme Foo[F[_], T]. C'est le genre d'un type comme (dans Haskell) newtype Twice f a = Twice (f (f a))(par exemple, Twice Maybe IntMaybe (Maybe Int), Twice [] Char[[Char]]) ou quelque chose de plus intéressant comme la monade libre data Free f a = Pure a | Free (f (Free f a)).
Jon Purdy
37

Je dirais: Un type plus kinded résumés sur un constructeur de type. Par exemple, considérez

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

Voici Functorun "type de type supérieur" (tel qu'utilisé dans le document "Génériques d'un type supérieur" ). Ce n'est pas un constructeur de type concret ("de premier ordre") comme List(qui résume uniquement les types appropriés). Il résume tous les constructeurs de type unaire ("de premier ordre") (comme indiqué par F[_]).

Ou pour le dire autrement: En Java, nous avons clairement des constructeurs de type (par exemple List<T>), mais nous n'avons pas de "types de type supérieur", parce que nous ne pouvons pas les abstraire (par exemple, nous ne pouvons pas écrire l' Functorinterface 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 de type supérieur".

Landei
la source
C'est ce que je pensais, mais cela semble contredire la réponse de Jon, où un "constructeur de type concret" est déjà un "type de type supérieur".
Lutz
3
Oui. Selon la réponse de Jon (si je comprends bien), List<T>Java serait un constructeur de type unaire car il en a clairement le genre * -> *. Ce qui manque dans la réponse de Jon, c'est que vous devez être capable d'abstraire sur le "tout" (et pas seulement sur le second *comme en Java) afin de l'appeler un type de type supérieur.
Landei
@Landai: l'article Scala pour les programmeurs génériques dans la section 4.3 suggère que le trait Iterable [A, Container [_]] est un type de type supérieur (bien qu'il ne soit pas clair si Iterator ou Container est destiné) où, de l'autre côté, vero690 dans la section 2.3.1 utilise le terme constructeur de type supérieur pour quelque chose comme (* -> *) -> * (opérateur de type paramétré avec un constructeur de type supérieur) qui ressemble à l'itérateur ou à votre trait Functor.
Lutz
1
C'est probablement vrai, mais je pense que nous commençons à couper les cheveux ici. Le point important concernant les types de types supérieurs est que non seulement les constructeurs de types sont impliqués (polymorphisme de constructeur de type un ordre), mais que nous sommes en mesure d'abstraire sur le type concret de ces constructeurs de type (polymorphisme de constructeur de type d'ordre supérieur). Nous avons la possibilité d'abstraire tout ce que nous voulons sans restrictions (concernant les types et les constructeurs de types), ce qui rend moins intéressant de nommer toutes les versions possibles de cette fonctionnalité. Et ça me fait mal au cerveau.
Landei
2
En général, il est important de distinguer les définitions et les références ici. La définition def succ(x: Int) = x+1introduit le "constructeur de valeur" (voir mon autre réponse pour ce que je veux dire par là) succ(personne ne se réfèrerait à cette valeur comme succ (x: Int)). Par analogie, Functorle type (en fait de type supérieur) est-il défini dans votre réponse. Encore une fois, vous ne devriez pas vous y référer comme Functor[F[_]](ce qui est F? Ce qui est _? Ils ne sont pas dans la portée! Malheureusement, le sucre syntaxique pour les existentiels brouille les eaux ici en faisant F[_]court pour F[T forSome {type T}])
Adriaan Moors
1

Scala REPL fournit une :kindcommande 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.

Le :helpfournit des définitions claires, donc je pense 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.
Mario Galic
la source