Was ist ein höherwertiger Typ in Scala?

275

Im Internet finden Sie Folgendes:

  1. Höher sortierter Typ == Typ Konstruktor?

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

    Einige sagen, dies sei ein höherwertiger Typ, da er über Typen abstrahiert, die der Definition entsprechen würden.

    Höher sortierte Typen sind Typen, die andere Typen annehmen und einen neuen Typ erstellen

    Diese werden jedoch auch als Typkonstruktor bezeichnet . (Zum Beispiel in Programmieren in Scala ).

  2. Höher sortierter Typ == Typkonstruktor, der den Typkonstruktor als Typparameter verwendet?

    In der Zeitung Generika höherer Art können Sie lesen

    ... Typen, die über Typen abstrahieren, die über Typen abstrahieren ('Typen höherer Art') ... "

    was darauf hindeutet

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

    ist ein höherwertiger Typ.

Also in diesem Sinne ist es schwierig , zu unterscheiden zwischen Typkonstruktor , höherer kinded Art und Typkonstruktor der Typkonstruktoren als Typ - Parameter nimmt daher die Frage oben.

Lutz
quelle
Landei's Functor als Beispiel hinzugefügt.
Lutz

Antworten:

284

Lassen Sie mich etwas von dieser Verwirrung wettmachen, indem ich mit einer gewissen Begriffsklärung einspringe. Ich verwende gerne die Analogie zur Wertebene, um dies zu erklären, da die Leute eher damit vertraut sind.

Ein Typkonstruktor ist ein Typ, den Sie auf Typargumente anwenden können, um einen Typ zu "konstruieren".

Ein Wertekonstruktor ist ein Wert, den Sie auf Wertargumente anwenden können, um einen Wert zu "konstruieren".

Wertekonstruktoren werden normalerweise als "Funktionen" oder "Methoden" bezeichnet. Diese "Konstruktoren" werden auch als "polymorph" (weil sie verwendet werden können, um "Zeug" unterschiedlicher "Form" zu konstruieren) oder "Abstraktionen" (da sie über das abstrahieren, was zwischen verschiedenen polymorphen Instanziierungen variiert) bezeichnet.

Im Kontext von Abstraktion / Polymorphismus bezieht sich erste Ordnung auf die "einmalige Verwendung" von Abstraktion: Sie abstrahieren einmal über einen Typ, aber dieser Typ selbst kann nicht über irgendetwas abstrahieren. Java 5-Generika sind erster Ordnung.

Die Interpretation der obigen Charakterisierungen von Abstraktionen erster Ordnung ist:

Ein Typkonstruktor ist ein Typ, den Sie auf geeignete Typargumente anwenden können, um einen geeigneten Typ zu "konstruieren".

Ein Wertekonstruktor ist ein Wert, den Sie auf geeignete Wertargumente anwenden können, um einen geeigneten Wert zu "konstruieren".

Um zu betonen, dass es sich nicht um eine Abstraktion handelt (ich denke, Sie könnten dies als "nullter Ordnung" bezeichnen, aber ich habe nicht gesehen, dass dies irgendwo verwendet wird), wie zum Beispiel den Wert 1oder den Typ String, sagen wir normalerweise, dass etwas ein "richtiger" Wert oder Typ ist.

Ein geeigneter Wert ist "sofort verwendbar" in dem Sinne, dass er nicht auf Argumente wartet (er abstrahiert nicht über sie). Stellen Sie sich diese als Werte vor, die Sie leicht drucken / überprüfen können (das Serialisieren einer Funktion ist Betrug!).

Ein richtiger Typ ist ein Typ, der Werte klassifiziert (einschließlich Wertekonstruktoren). Typkonstruktoren klassifizieren keine Werte (sie müssen zuerst auf die richtigen Typargumente angewendet werden, um einen richtigen Typ zu erhalten). Um einen Typ zu instanziieren, ist es notwendig (aber nicht ausreichend), dass es sich um einen richtigen Typ handelt. (Es kann sich um eine abstrakte Klasse handeln oder um eine Klasse, auf die Sie keinen Zugriff haben.)

"Höhere Ordnung" ist einfach ein Oberbegriff, der die wiederholte Verwendung von Polymorphismus / Abstraktion bedeutet. Dies gilt auch für polymorphe Typen und Werte. Konkret abstrahiert eine Abstraktion höherer Ordnung über etwas, das über etwas abstrahiert. Für Typen ist der Begriff "höherwertig" eine Spezialversion der allgemeineren "übergeordneten Ordnung".

Somit wird die übergeordnete Version unserer Charakterisierung:

Ein Typkonstruktor ist ein Typ, den Sie auf Typargumente (richtige Typen oder Typkonstruktoren) anwenden können, um einen richtigen Typ (Konstruktor) zu "konstruieren".

Ein Wertekonstruktor ist ein Wert, den Sie auf Wertargumente (Eigenwerte oder Wertekonstruktoren) anwenden können, um einen Eigenwert (Konstruktor) zu "konstruieren".

"Höhere Ordnung" bedeutet also einfach, dass Sie es wirklich meinen, wenn Sie "über X abstrahieren" sagen! Das X, über das abstrahiert wird, verliert nicht seine eigenen "Abstraktionsrechte": Es kann alles abstrahieren, was es will. (Übrigens verwende ich hier das Verb "abstrakt", um zu bedeuten: etwas wegzulassen, das für die Definition eines Wertes oder Typs nicht wesentlich ist, damit es vom Benutzer der Abstraktion als Argument variiert / bereitgestellt werden kann .)

Hier sind einige Beispiele (inspiriert von Lutz 'Fragen per E-Mail) für richtige Werte und Typen erster und höherer Ordnung:

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

Wo die verwendeten Klassen definiert wurden als:

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

Um die Indirektion durch das Definieren von Klassen zu vermeiden, müssen Sie anonyme Typfunktionen ausdrücken, die in Scala nicht direkt ausgedrückt werden können. Sie können jedoch Strukturtypen ohne zu großen syntaktischen Aufwand verwenden (der Stil ist auf https://stackoverflow.com zurückzuführen / users / 160378 / retronym afaik):

In einer hypothetischen zukünftigen Version von Scala, die anonyme Typfunktionen unterstützt, können Sie diese letzte Zeile aus den Beispielen auf Folgendes verkürzen:

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

(Persönlich bedauere ich, dass ich jemals über "höherwertige Typen" gesprochen habe, sie sind schließlich nur Typen! Wenn Sie unbedingt unterscheiden müssen, schlage ich vor, Dinge wie "Typkonstruktorparameter", "Typkonstruktormitglied" zu sagen. oder "Typkonstruktor-Alias", um zu betonen, dass es sich nicht nur um richtige Typen handelt.)

ps: Um die Sache noch weiter zu verkomplizieren, ist "polymorph" auf andere Weise mehrdeutig, da ein polymorpher Typ manchmal einen universell quantifizierten Typ bedeutet, z. B. Forall T, T => Teinen geeigneten Typ, da er polymorphe Werte klassifiziert (in Scala kann dieser Wert sein geschrieben als Strukturtyp {def apply[T](x: T): T = x})

Adriaan Mauren
quelle
1
siehe auch: adriaanm.github.com/research/2010/10/06/…
Adriaan Moors
5
Adriaans Artikel "Type Constructor Polymorphism" jetzt unter adriaanm.github.com/research/2010/10/06/…
Steven Shaw
Ich lese es immer wieder als höhere Verwandtschaft und stelle mir einen verwandten Geist vor
Janac Meena
110

(Diese Antwort ist ein Versuch, die Antwort von Adriaan Moors mit einigen grafischen und historischen Informationen zu dekorieren.)

Höher sortierte Typen sind seit 2.5 Teil von Scala.

  • Zuvor erlaubte Scala als Java bisher nicht, den Typkonstruktor ("Generika" in Java) als Typparameter für einen Typkonstruktor zu verwenden. z.B

     trait Monad [M[_]]

    war nicht möglich.

    In Scala 2.5 wurde das Typensystem um die Möglichkeit erweitert, Typen auf einer höheren Ebene zu klassifizieren (bekannt als Typkonstruktor-Polymorphismus ). Diese Klassifikationen werden als Arten bezeichnet.

    Typ und Art realtion, ** abgeleitet ** von "Generika einer höheren Art" (Bild von Generika höherer Art abgeleitet )

    Die Konsequenz ist, dass der Typkonstruktor (z. B. List) genauso wie andere Typen in der Position der Typparameter von Typkonstruktoren verwendet werden kann und daher seit Scala 2.5 zu erstklassigen Typen wird. (Ähnlich wie Funktionen, die in Scala erstklassige Werte sind).

    Im Kontext eines Typsystems, das höhere Arten unterstützt, können wir geeignete Typen , Typen wie Intoder List[Int]von Typen erster Ordnung wie Listund Typen höherer Art wie Functoroder Monad(Typen, die über Typen abstrahieren, die über Typen abstrahieren) unterscheiden.

    Das Typsystem von Java auf der anderen Seite unterstützt keine Arten und hat daher keine Typen einer "höheren Art".

    Dies muss also vor dem Hintergrund des unterstützenden Typsystems gesehen werden.

  • Im Fall von Scala sehen Sie häufig Beispiele für einen Typkonstruktor wie

     trait Iterable[A, Container[_]]

    mit der Überschrift "Höher sortierte Typen", zB in Scala für generische Programmierer, Abschnitt 4.3

    Dies ist manchmal irreführend, weil viele Containerals höherwertiger Typ bezeichnen und nicht Iterable, aber was genauer ist, ist:

    die Verwendung Containereines Typkonstruktorparameters eines Typs höherer Art (höherer Ordnung) als Typ hier Iterable.

Lutz
quelle
80

Die Art von gewöhnlichen Typen wie Intund Char, deren Instanzen Werte sind, ist *. Die Art von unären Typkonstruktoren wie Maybeist * -> *; Konstruktoren vom binären Typ wie Eitherhaben ( Curry- ) Art * -> * -> *und so weiter. Sie können Typen wie Maybeund anzeigenEither als Funktionen auf : Sie nehmen einen oder mehrere Typen an und geben einen Typ zurück.

Eine Funktion ist höherer Ordnung, wenn sie eine Ordnung größer als 1 hat, wobei die Reihenfolge (informell) die Verschachtelungstiefe der Funktionspfeile links ist:

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

Kurz gesagt, ein Typ höherer Ordnung ist nur eine Funktion höherer Ordnung auf Typebene .

  • Bestellung 0: Int :: *
  • Bestellung 1: Maybe :: * -> *
  • Reihenfolge 2: Functor :: (* -> *) -> Constraint- höherwertig: Konvertiert unäre Typkonstruktoren in Typklasseneinschränkungen
Jon Purdy
quelle
Ok, ich habe es verstanden, was wäre dann ein Beispiel in Scala für (* ⇒ *) ⇒ * und (* ⇒ *) ⇒ (* ⇒ *)? Würde der Functor of Landei in die erste Kategorie oder eher in die zweite passen?
Lutz
1
@lutz: Es wäre in der ersten Kategorie: FunctorErzeugt einen richtigen Typ ( naja , Merkmal, aber die gleiche Idee) Functor[F[_]]aus einem Typkonstruktor F.
Jon Purdy
1
@ Jon: Ein sehr aufschlussreicher Beitrag, danke. Kann der (* => *) => (* => *)Typkonverter in Scala ausgedrückt werden? Wenn nicht, in einer anderen Sprache?
Eugen Labun
@ JonPurdy Der Vergleich zwischen * ⇒ * ⇒ *mit Curry ist sehr hilfreich. Vielen Dank!
Lifu Huang
(* ⇒ *) ⇒ (* ⇒ *)kann auch geschrieben werden (* ⇒ *) ⇒ * ⇒ *. Es kann in Scala wie ausgedrückt werden Foo[F[_], T]. Dies ist die Art eines Typs wie (in Haskell) newtype Twice f a = Twice (f (f a))(z. B. Twice Maybe IntMaybe (Maybe Int), Twice [] Char[[Char]]) oder etwas Interessanteres wie die freie Monade data Free f a = Pure a | Free (f (Free f a)).
Jon Purdy
37

Ich würde sagen: Ein höherwertiger Typ abstrahiert über einen Typkonstruktor . ZB überlegen

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

Hier Functorist ein "höherwertiger Typ" (wie er im "Generics of a Higher Kind" -Papier verwendet wird ). Es ist kein konkreter Konstruktor vom Typ "erster Ordnung" List(der nur über die richtigen Typen abstrahiert). Es abstrahiert über alle unären Konstruktoren ("erster Ordnung") (wie mit bezeichnet F[_]).

Oder List<T>anders ausgedrückt: In Java haben wir eindeutig Typkonstruktoren (z. B. ), aber wir haben keine "höher sortierten Typen", weil wir nicht über sie abstrahieren können (z. B. können wir Functordie oben definierte Schnittstelle nicht schreiben - zumindest nicht direkt ).

Der Begriff "Polymorphismus höherer Ordnung (Typkonstruktor)" wird verwendet, um Systeme zu beschreiben, die "Typen höherer Ordnung" unterstützen.

Landei
quelle
Dies ist, was ich dachte, aber es scheint Jons Antwort zu widersprechen, wo ein "konkreter Typkonstruktor" bereits ein "höherwertiger Typ" ist.
Lutz
3
Ja. Nach Jons Antwort (so wie ich es verstehe) List<T>wäre Java ein unärer Typkonstruktor, da es eindeutig die Art hat * -> *. Was in Jons Antwort fehlt, ist, dass Sie in der Lage sein müssen, über das "Ganze" (und nicht nur über das zweite *wie in Java) zu abstrahieren , um es einen höherwertigen Typ zu nennen.
Landei
@Landai: Das Papier Scala für generische Programmierer in Abschnitt 4.3 schlägt vor, dass das Merkmal Iterable [A, Container [_]] ein höherwertiger Typ ist (obwohl nicht klar ist, ob Iterator oder Container gemeint ist), wo auf der anderen Seite vero690 in In Abschnitt 2.3.1 wird der Begriff höherwertiger Typkonstruktor für etwas wie (* -> *) -> * (mit dem Typkonstruktor höherer Ordnung parametrisierter Typoperator) verwendet, der dem Iterator oder Ihrem Functor-Merkmal ähnelt.
Lutz
1
Das ist wahrscheinlich richtig, aber ich denke, wir fangen hier an, Haare zu spalten. Der wichtige Punkt in Bezug auf höherwertige Typen ist, dass nicht nur Typkonstruktoren beteiligt sind (Typ-1-Typ-Konstruktor-Polymorphismus), sondern dass wir in der Lage sind, über den konkreten Typ dieser Typ-Konstruktoren zu abstrahieren (Typ-Konstruktor-Polymorphismus höherer Ordnung). Wir haben die Möglichkeit, ohne Einschränkungen (was Typen und Typkonstruktoren betrifft) über alles zu abstrahieren, was wir wollen, was es weniger interessant macht, alle möglichen Versionen dieser Funktion zu benennen. Und es tut meinem Gehirn weh.
Landei
2
Im Allgemeinen ist es wichtig, hier Definitionen und Referenzen zu unterscheiden. Die Definition def succ(x: Int) = x+1führt den "Wertekonstruktor" ein (siehe meine andere Antwort für das, was ich damit meine) succ(niemand würde diesen Wert als succ (x: Int) bezeichnen). In Analogie dazuFunctor ist der (in der Tat höherwertige) Typ in Ihrer Antwort definiert. Auch hier sollten Sie es nicht als Functor[F[_]](was ist F? Was ist _? Sie sind nicht im Geltungsbereich! Leider trübt der syntaktische Zucker für Existenziale das Wasser hier, indem er F[_]kurz macht F[T forSome {type T}]) bezeichnen
Adriaan Moors
0

Scala REPL bietet :kindBefehl, der

scala> :help kind

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

Zum Beispiel,

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.

Das :helpenthält klare Definitionen, daher denke ich, dass es sich lohnt, es hier in seiner Gesamtheit zu veröffentlichen (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
quelle