Höhere Kinded Typen in Scala

Question

Ich bin in Scala Buch durch die funktionale Programmierung zu lesen und im Monoide Kapitel, sprechen sie über eine Monoid-Schnittstelle, die wie folgt aussieht:

trait Monoid[A] { 
def op(a1: A, a2: A): A 
def zero: A 
} 

Später, sie spezifische Monoid definieren Instanzen durch Erweiterung dieser Schnittstelle. Zum Beispiel.,

val intMonoid = new Monoid[Int] { 
    ... 
} 

val listMonoid = new Monoid[List[Int]] { 
    ... 
} 

Ein paar mehr Seiten, die ich durch dieses Kapitel las 10, stoße ich auf ‚höhere kinded Typen‘, die nach dem Buch jede Art ist, dass es selbst ein Typ ist, die anderen Arten nehmen .

trait Foldable[F[_]] { 
... 
... 
} 

So ist der Zug nach faltbar ist das Buch eines höherer kinded Typ. Meine Frage ist, das Monoid [A] für mich passt auch zu der Definition des 'höher kinkenden Typs', da es eine Liste [A] aufnehmen kann. Ist mein Verständnis richtig? Wenn nicht, was macht höhere Arten in Scala zu einem höheren Typus?

Edit: So ein unärer Typkonstruktor nimmt ein Argument und erzeugt einen Typ. Was ist nun mit diesem Fall hier?

def listMonoid[A] = new Monoid[List[A]] { 
    ... 
    ... 
} 

Also ist meine ListMonoid-Funktion ein HKT?

Answer 1

einige Begriffe:

• richtigen Typs (z.B. Int)
• Typs erster Ordnung (z.B. List [_]); wir könnten auch erster Ordnung sagen Art
• höherer kinded Typ (zB Monad [M [_])

Wenn Sie

trait Monoid[A] { 
    def op(a1: A, a2: A): A 
    def zero: A 
} 

val listMonoid = new Monoid[List[Int]] { 
    def op(l: List[Int], l2: List[Int]) = List(1,2) 
    def zero = List(1,2) 
} 

sagen Sie Parametrisierung der Monoid Zug mit irgendeiner Art A , die (wie Sie bemerkt haben) ein einfacher Typ sein kann, auch als richtiger Typ bekannt sein kann (zB Int) oder ein parametrisierter Typ (zB List[Int] oder sogar List[Set[Map[Int, Int]]). Dies macht Monoid zu einem Typ erster Ordnung. Wir können auch sagen, dass es ein unärer Typkonstruktor ist - es braucht einen Typ, um den endgültigen Typ zu erzeugen.

Im Gegensatz zu Monoid müssen einige Abstraktionen (z. B. Monad) durch einen Typkonstruktor parametrisiert werden. Int funktioniert nicht mehr. Es muss "ein Typ sein, der einen anderen Typ erzeugen kann". Abstraktion, die durch einen Typkonstruktor parametrisiert wird (dh durch einen "Typ erster Ordnung" parametrisiert wird), ist ein höher-kinded Typ. Hier ein Beispiel:

trait Monad[M[_]] { 
    def op[A, B](m: M[A], f: A => M[B]): M[B] 
    def zero[A](a: A): M[A] 
} 

object ListMonad extends Monad[List] { 
    def op[A, B](m: List[A], f: A => List[B]) = m.flatMap(f) 
    def zero[A](a: A) = List[A](a) 
} 

val listMonad = ListMonad.zero(42) 
val result = ListMonad.op(listMonad, (i: Int) => List(i - 1, i, i + 1)) 

// result = List(41, 42, 43) 

So wird Monad parametrisiert durch einen erste Ordnung Typen (a einstelliger Typkonstruktor), dieMonad selbst einen höheren kinded Typen macht.

Beachten Sie, wie Monad wirklich über den „inneren Typen“ selbst auf der Ebene der Klassen ist es egal, wie sie von den Methoden definiert werden op und zero. Sie könnten auch trait Monad[M[A]] sagen und den Typ A am Definitionspunkt der Klasse (z.B.fixiere es auf Int), aber dann verlierst du die Flexibilität (deine wird dann nur in der Lage sein, eine List[Int] zu konstruieren und eine andere Klasse für zB List[String] zu benötigen).

Dies ist anders als ein Monoid, das kein höher-kinded Typ ist; Es benötigt keinen Typkonstruktor, um einen Typ zu erzeugen. Wenn es benötigt wird, dann könnten Sie niemals ein, sagen wir, Monoid[Int] haben, weil Int kein Typkonstruktor ist.

Es ist irgendwie eine Ein-Richtungs-Beziehung - wenn Sie einen einfachen Typ A haben, ist es jede Art von beliebiger Reihenfolge repräsentiert, so dass in diesem Fall List[Int] als vollkommen gut dienen kann A (so kann List[Set[Option[Try[Int]]]] Aber wenn Sie haben. ein Typ erster Ordnung M [A], man kann ihn nicht in einen einfachen konkreten Typ wie Int umwandeln. Er muss ein Typkonstruktor sein. Monoid kann mit Ints arbeiten, aber Monad kann nicht; monad braucht einen "Container" "wie Option[_], Try[_], List[_], Set[_], etc. Es ist wie Subtyping - Banana kann als eine Frucht dienen, aber Obst kann nicht als eine Banane dienen. Richtige Art kann alles sein; erster Ordnung Typ benötigt einen Typ, um eine Art zu produzieren; Höherer Typ benötigt einen Typ erster Ordnung, um einen Typ zu erstellen, usw.

Es ist auch wichtig zu beachten, dass es ein unärer Typ Konstruktor ist, was bedeutet, dass es nur einen Typ braucht (anders als z. Karte, die zwei nimmt). Typkonstruktoren sind oft mit Sternchen und Pfeile dargestellt:

• einstellige erster Ordnung Typkonstruktor ist * -> * (es einen einzigen Typ nimmt und die letzte Art, zB Set)
• binäre erster Ordnung Typkonstruktor ist * -> * -> * (a binary Typkonstruktor nimmt zwei Typen die endgültige Typ herzustellen, zB Map)
• unären höherer kinded Typ ist (* -> *) -> * (nimmt einen einzelnen unären Typkonstruktor die letzte Art zu erzeugen, beispielsweise Monad)

usw.

So nimmt der Typ erster Ordnung einen einfachen/konkreten/richtigen Typ an und erzeugt den endgültigen Typ, während der höherwertige Typ eine Ebene höher geht; Es braucht einen Typ erster Ordnung, um den endgültigen Typ zu erzeugen.

EDIT:

beantworten Ihre Frage in "Bearbeiten" Teil: OK, ich glaube, ich weiß, was Sie ist verwirrend. listMonoid ist kein Typ, daher kann es kein Typ höherer Ordnung sein. Es ist eine Methode. Monad[List[Int]] ist ein vollständig aufgelöster Typ. ist auch vollständig gelöst. Jedoch ist Monad selbst ein Typ höherer Ordnung.

Lassen Sie mich die Parallelen zu Funktionen ziehen. Wenn Sie eine Funktion foo(x: Int) haben, dann führen Funktionsaufrufe wie foo(42) oder foo(someIntegerValue) zu konkreten Werten. Diese sind analog zu Monad[List[Int]] und . foo selbst ist jedoch eine Funktion, genauso wie Monad selbst ein Typenkonstruktor ist.

Wenn foo einen einfachen Wert (keine Funktion) hat, ist es eine Funktion erster Ordnung; Wenn es eine Funktion annimmt oder zurückgibt, ist es eine Funktion höherer Ordnung. Das Gleiche gilt für Typkonstruktoren. Wenn es einen einfachen Typ benötigt, handelt es sich um einen Konstruktor erster Ordnung. Beispiel: List. Wenn es einen anderen Typkonstruktor benötigt, handelt es sich um einen Typkonstruktor höherer Ordnung (auch bekannt als höherer Typ).Beispiel: Monad.

Nicht aufgelöste Typen mit Typkonstruktoren mischen. Es ist sinnvoll zu überlegen, ob die Funktion foo höherrangig ist oder nicht; Dies hängt von seinen Argumenten und seinem Rückgabetyp ab. Aber es macht keinen Sinn zu denken, ob foo(42) höherrangig ist oder nicht; Dies ist keine Funktion, sondern eine Funktionsanwendung, die zu einem Wert führt. Monad[List[Int]] ist kein Typkonstruktor, sondern eine Anwendung des Typkonstruktors List auf den Typkonstruktor Monad (der höherwertig ist). Ähnlich ist Monoid[List[Int]] kein Typ-Constructor, sondern eine Anwendung vom Typ List[Int] an den Typkonstruktor Monoid (der erster Ordnung ist). Typ Konstruktoren von höherer Ordnung werden HKT genannt. Es macht keinen Sinn, über HKT zu sprechen und auf einen konkreten aufgelösten Typ zu zeigen (der als Ergebnis der Anwendung eines Typkonstruktors erstellt wurde).