Was bewirkt das Schlüsselwort `forall` in Haskell/GHC?

Question

Ich beginne zu verstehen, wie die forall Schlüsselwort wird in so genannten "existenziellen Typen" wie diesem verwendet:

data ShowBox = forall s. Show s => SB s

Dies ist jedoch nur eine Teilmenge dessen, wie forall verwendet wird, und ich kann mir einfach nicht vorstellen, dass es in solchen Dingen verwendet wird:

runST :: forall a. (forall s. ST s a) -> a

Oder zu erklären, warum diese unterschiedlich sind:

foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

Oder die ganze RankNTypes Zeug...

Ich neige dazu, klares, jargonfreies Englisch zu bevorzugen und nicht die Art von Sprache, die im akademischen Umfeld üblich ist. Die meisten Erklärungen, die ich zu diesem Thema zu lesen versuche (die, die ich über Suchmaschinen finden kann), haben diese Probleme:

1. Sie sind unvollständig. Sie erklären einen Teil der Verwendung dieses Schlüsselworts (wie "existentielle Typen"), was mich glücklich macht, bis ich Code lese, der es auf eine völlig andere Weise verwendet (wie runST , foo y bar oben).
2. Sie sind vollgepackt mit Annahmen, dass ich den neuesten Stand der diskreten Mathematik, der Kategorientheorie oder der abstrakten Algebra gelesen habe, der diese Woche populär ist. (Wenn ich nie die Worte "konsultieren Sie das Papier" lese was auch immer für die Einzelheiten der Umsetzung" noch einmal nachfragen, wird es zu früh sein).
3. Sie sind in einer Art und Weise geschrieben, die häufig selbst einfache Konzepte in eine verschlungene und gebrochene Grammatik und Semantik verwandelt.

Also...

Nun zu der eigentlichen Frage. Kann jemand vollständig erklären, wie die forall Schlüsselwort in klarem, einfachem Englisch (oder, falls es irgendwo existiert, weisen Sie auf eine solche klare Erklärung hin, die ich übersehen habe), die nicht voraussetzt, dass ich ein Mathematiker bin, der in den Fachjargon vertieft ist?

---

Bearbeitet um hinzuzufügen:

Es gab zwei herausragende Antworten unter den höherwertigen Antworten, aber leider kann ich nur eine als beste auswählen. Normans Antwort war detailliert und nützlich und erklärte die Dinge auf eine Weise, die einige der theoretischen Grundlagen der forall und zeigte mir gleichzeitig einige der praktischen Auswirkungen davon. yairchu's Antwort deckte einen Bereich ab, den sonst niemand erwähnte (scoped type variables) und illustrierte alle Konzepte mit Code und einer GHCi-Sitzung. Wäre es möglich, beides als das Beste auszuwählen, würde ich es tun. Leider kann ich das nicht, und nachdem ich mir beide Antworten genau angesehen habe, bin ich zu dem Schluss gekommen, dass die von yairchu aufgrund des anschaulichen Codes und der beigefügten Erklärung etwas besser ist als die von Norman. Das ist allerdings ein bisschen unfair, denn ich brauchte wirklich beide Antworten, um die Sache so weit zu verstehen, dass forall lässt mich nicht mit einem leisen Gefühl des Grauens zurück, wenn ich es in einer Typoskription sehe.

Answer 1

Meine ursprüngliche Antwort:

Kann jemand das Schlüsselwort forall in klarem, einfachem Englisch vollständig erklären?

Wie Norman anmerkt, ist es sehr schwierig, eine klare, einfache englische Erklärung zu geben eines Fachbegriffs aus der Typentheorie zu erklären. Wir versuchen es aber alle.

Bei 'forall' gibt es eigentlich nur eines zu beachten: es bindet Typen an einen Bereich . Wenn man das einmal verstanden hat, ist alles ziemlich einfach. Es ist das Äquivalent von 'lambda' (oder einer Form von 'let') auf der Typenebene - Norman Ramsey verwendet den Begriff "links"/"oben", um dasselbe Konzept des Geltungsbereichs in seine ausgezeichnete Antwort .

Die meisten Verwendungen von 'forall' sind sehr einfach, und Sie können sie in die GHC-Benutzerhandbuch, S7.8 insbesondere die ausgezeichnete S7.8.5 bei verschachtelten Formen von 'forall'.

In Haskell lassen wir normalerweise den Binder für Typen weg, wenn der Typ universell quanitifiziert ist, etwa so:

length :: forall a. [a] -> Int

ist gleichbedeutend mit:

length :: [a] -> Int

Das war's.

Da Sie jetzt Typvariablen an einen Bereich binden können, können Sie andere Bereiche haben als die oberste Ebene (" allgemeingültig quantifiziert "), wie in Ihrem ersten Beispiel, wobei die Typvariable nur innerhalb der Datenstruktur sichtbar ist. Dies ermöglicht für versteckte Typen (" existentielle Typen "). Oder wir können willkürlich Verschachtelung von Bindungen ("Rang N-Typen").

Um Typensysteme zu verstehen, müssen Sie einige Fachausdrücke lernen. Das ist liegt in der Natur der Computerwissenschaft. Einfache Anwendungen, wie die obige, sollten jedoch Analogie zu "let" auf der Werteebene intuitiv verstanden werden können. A gute Einführung ist Launchbury und Peyton Jones .

Answer 2

Im Folgenden finden Sie eine kurze Erklärung in einfachen Worten, mit denen Sie wahrscheinlich bereits vertraut sind.

Les forall Schlüsselwort wird in Haskell eigentlich nur auf eine Weise verwendet. Es bedeutet immer das Gleiche, wenn Sie es sehen.

Universelle Quantifizierung

A universell quantifizierbarer Typ ist ein Typ der Form forall a. f a . Einen Wert dieses Typs kann man sich vorstellen als eine Funktion die eine Typ a als sein Argument und gibt ein Wert vom Typ f a . Nur werden in Haskell diese Typargumente implizit vom Typsystem übergeben. Diese "Funktion" muss Ihnen den gleichen Wert liefern, egal welchen Typ sie erhält, also ist der Wert polymorph .

Betrachten wir zum Beispiel den Typ forall a. [a] . Ein Wert dieses Typs nimmt einen anderen Typ an a und gibt Ihnen eine Liste von Elementen desselben Typs zurück a . Es gibt natürlich nur eine mögliche Umsetzung. Sie müsste Ihnen die leere Liste liefern, weil a kann absolut jeder Typ sein. Die leere Liste ist der einzige Listenwert, der in seinem Elementtyp polymorph ist (da er keine Elemente hat).

Oder der Typ forall a. a -> a . Der Aufrufer einer solchen Funktion gibt sowohl einen Typ a und einen Wert des Typs a . Die Implementierung muss dann einen Wert desselben Typs zurückgeben a . Auch hier gibt es nur eine mögliche Implementierung. Sie müsste den gleichen Wert zurückgeben, der ihr gegeben wurde.

Existenzielle Quantifizierung

Eine existentiell quantifizierter Typ hätte die Form exists a. f a , wenn Haskell diese Notation unterstützen würde. Einen Wert dieses Typs kann man sich vorstellen als ein Paar (oder ein "Produkt"), bestehend aus einer Art a und einen Wert des Typs f a .

Wenn Sie zum Beispiel einen Wert vom Typ exists a. [a] haben Sie eine Liste von Elementen eines bestimmten Typs. Das kann ein beliebiger Typ sein, aber auch wenn man nicht weiß, welcher Typ es ist, kann man mit einer solchen Liste eine Menge anstellen. Man könnte sie umkehren, die Anzahl der Elemente zählen oder jede andere Listenoperation durchführen, die nicht vom Typ der Elemente abhängt.

OK, warten Sie einen Moment. Warum verwendet Haskell forall um einen "existentiellen" Typ wie den folgenden zu bezeichnen?

data ShowBox = forall s. Show s => SB s

Das kann verwirrend sein, aber es beschreibt wirklich die Typ des Datenkonstruktors SB :

SB :: forall s. Show s => s -> ShowBox

Einmal konstruiert, können Sie sich einen Wert des Typs ShowBox als aus zwei Dingen bestehend. Es ist eine Art s zusammen mit einem Wert des Typs s . Mit anderen Worten, es handelt sich um einen Wert eines existentiell quantifizierten Typs. ShowBox könnte eigentlich geschrieben werden als exists s. Show s => s , wenn Haskell diese Notation unterstützen würde.

runST und Freunde

Inwiefern unterscheiden sie sich dann?

foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))

Nehmen wir zunächst bar . Sie nimmt einen Typ a und eine Funktion des Typs a -> a und erzeugt einen Wert des Typs (Char, Bool) . Wir könnten wählen Int als die a und geben ihm eine Funktion des Typs Int -> Int zum Beispiel. Aber foo ist anders. Sie erfordert, dass die Umsetzung von foo in der Lage sein, der Funktion, die wir ihr geben, jeden beliebigen Typ zu übergeben. Die einzige Funktion, die wir ihr vernünftigerweise geben können, ist also id .

Wir sollten nun in der Lage sein, die Bedeutung des Typs der runST :

runST :: forall a. (forall s. ST s a) -> a

Así que runST muss in der Lage sein, einen Wert des Typs a unabhängig davon, welche Art wir als a . Dazu verwendet es ein Argument vom Typ forall s. ST s a die sicherlich irgendwie die a . Darüber hinaus muss er einen Wert des Typs a unabhängig von der Art der Implementierung von runST beschließt, als s .

Somit ist die runST Funktion sagt zu Ihnen: "Sie können den Typ wählen a Solange ich den Typ wählen kann s ."

OK, und weiter? Der Vorteil ist, dass dies den Aufrufer von runST dass der Typ a kann nicht mit dem Typ s überhaupt nicht, da Sie nicht wissen, welche Art von s sein wird. Sie können ihm keinen Wert vom Typ ST s [s] zum Beispiel. In der Praxis bedeutet dies, dass die Umsetzung von runST kann wissen, dass jeder Wert, der den Typ s ist lokal für seine eigene Implementierung, so dass es Dinge tun kann, die es sonst nicht dürfte, wie z. B. sie an Ort und Stelle zu mutieren. Der Typ garantiert, dass die Mutation lokal für die Implementierung von runST .

Die Art der runST ist ein Beispiel für eine polymorpher Typ Rang 2 weil der Typ seines Arguments ein forall Quantifizierer. Der Typ von foo ist ebenfalls von Rang 2. Ein gewöhnlicher polymorpher Typ, wie der von bar ist Rang 1, wird aber zu Rang 2, wenn die Typen der Argumente polymorph sein müssen und ihre eigenen forall Quantifizierer. Und wenn eine Funktion Argumente vom Rang 2 annimmt, dann ist ihr Typ vom Rang 3, und so weiter. Im Allgemeinen ist ein Typ, der polymorphe Argumente vom Rang n hat den Rang n + 1 .

Answer 3

Sie sind vollgepackt mit Annahmen, dass ich den neuesten Stand der diskreten Mathematik, der Kategorientheorie oder der abstrakten Algebra gelesen habe, der diese Woche populär ist. (Wenn ich nie wieder die Worte "konsultieren Sie das Papier, was auch immer für Details der Umsetzung" lesen werde, wird es zu früh sein.)

Äh, und was ist mit der einfachen Logik erster Ordnung? forall bezieht sich ziemlich eindeutig auf universelle Quantifizierung und in diesem Zusammenhang der Begriff existentiell macht ebenfalls mehr Sinn, obwohl es weniger umständlich wäre, wenn es eine exists Stichwort. Ob die Quantifizierung tatsächlich universell oder existentiell ist, hängt von der Platzierung des Quantifizierers im Verhältnis dazu ab, wo die Variablen auf welcher Seite eines Funktionspfeils verwendet werden, und das ist alles ein bisschen verwirrend.

Wenn Ihnen das nicht hilft oder Sie symbolische Logik nicht mögen, können Sie Typvariablen aus der Perspektive der funktionalen Programmierung einfach als (implizite) Typ Parameter für die Funktion. Funktionen, die Typ-Parameter in diesem Sinne annehmen, werden traditionell mit einem großen Lambda geschrieben, aus welchem Grund auch immer, das ich hier wie folgt schreibe /\ .

Betrachten Sie also die id Funktion:

id :: forall a. a -> a
id x = x

Wir können sie als Lambdas umschreiben, indem wir den "Typparameter" aus der Typsignatur herausnehmen und Inline-Typ-Annotationen hinzufügen:

id = /\a -> (\x -> x) :: a -> a

Hier ist das Gleiche zu sehen const :

const = /\a b -> (\x y -> x) :: a -> b -> a

Also Ihr bar Funktion könnte in etwa so aussehen:

bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool)

Beachten Sie, dass der Typ der Funktion, die an bar als Argument hängt ab von bar den Typ-Parameter. Stellen Sie sich vor, Sie hätten stattdessen etwas wie dieses:

bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool)

ここで bar2 ist die Anwendung der Funktion auf etwas vom Typ Char so geben bar2 jeder andere Typ-Parameter als Char wird einen Typfehler verursachen.

Auf der anderen Seite, hier ist, was foo aussehen könnte:

foo = (\f -> (f Char 't', f Bool True))

Anders als bar , foo nimmt eigentlich überhaupt keine Typparameter an! Sie nimmt eine Funktion, die selbst nimmt einen Typ-Parameter und wendet diese Funktion dann auf zwei verschiedene Typen.

Wenn Sie also eine forall in einer Typsignatur, betrachten Sie es einfach als lambda-Ausdruck für Typsignaturen . Genau wie bei normalen Lambdas ist der Geltungsbereich von forall erstreckt sich so weit wie möglich nach rechts, bis zu den einschließenden Klammern, und genau wie die in einem regulären Lambda gebundenen Variablen, werden die durch eine forall sind nur innerhalb des quantifizierten Ausdrucks gültig.

---

Post scriptum : Vielleicht fragen Sie sich - jetzt, wo wir über Funktionen nachdenken, die Typparameter annehmen, warum können wir nicht etwas Interessanteres mit diesen Parametern machen, als sie in eine Typsignatur zu packen? Die Antwort ist, dass wir das können!

Eine Funktion, die Typvariablen mit einem Label versieht und einen neuen Typ zurückgibt, ist eine Typkonstrukteur die man etwa so schreiben könnte:

Either = /\a b -> ...

Aber wir bräuchten eine völlig neue Notation, denn die Art und Weise, wie ein solcher Typ geschrieben wird, wie Either a b ist bereits ein Hinweis auf "die Funktion anwenden Either zu diesen Parametern".

Andererseits ist eine Funktion, die eine Art "Musterübereinstimmung" für ihre Typparameter herstellt und unterschiedliche Werte für verschiedene Typen zurückgibt, eine Methode einer Typklasse . Eine leichte Erweiterung meiner /\ Die obige Syntax legt etwas Ähnliches nahe:

fmap = /\ f a b -> case f of
    Maybe -> (\g x -> case x of
        Just y -> Just b g y
        Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b
    [] -> (\g x -> case x of
        (y:ys) -> g y : fmap [] a b g ys 
        []     -> [] b) :: (a -> b) -> [a] -> [b]

Ich persönlich glaube, ich bevorzuge die eigentliche Syntax von Haskell...

Eine Funktion, die mit ihren Typparametern "Mustervergleiche" durchführt und einen beliebigen, vorhandenen Typ zurückgibt, ist eine Typenfamilie o Funktionsabhängigkeit --Im ersten Fall sieht es sogar schon sehr nach einer Funktionsdefinition aus.

Answer 4

Kann jemand das forall-Schlüsselwort in klarem, einfachem Englisch vollständig erklären (oder, falls es irgendwo existiert, auf eine solche klare Erklärung hinweisen, die ich übersehen habe), die nicht voraussetzt, dass ich ein in den Fachjargon vertiefter Mathematiker bin?

Ich werde versuchen, nur die Bedeutung und vielleicht auch die Anwendung von forall im Kontext von Haskell und seinen Typsystemen.

Aber bevor Sie das verstehen, möchte ich Sie auf einen sehr verständlichen und schönen Vortrag von Runar Bjarnason mit dem Titel " Zwänge befreien, Freiheiten schränken ein ". Der Vortrag ist voll von Beispielen aus der realen Welt sowie von Beispielen in Scala, um diese Aussage zu untermauern, obwohl er nicht erwähnt forall . Ich werde versuchen, das zu erklären forall Perspektive unten.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Es ist sehr wichtig, diese Aussage zu verdauen und zu glauben, um mit der folgenden Erklärung fortzufahren, daher empfehle ich Ihnen dringend, sich den Vortrag (zumindest Teile davon) anzusehen.

Ein sehr gängiges Beispiel, das die Ausdruckskraft des Haskell-Typsystems zeigt, ist diese Typsignatur:

foo :: a -> a

Es wird gesagt, dass es bei dieser Typsignatur nur eine Funktion gibt, die diesen Typ erfüllen kann, und das ist die identity Funktion oder, was im Volksmund besser bekannt ist id .

In der Anfangsphase, als ich Haskell lernte, habe ich mich immer über die folgenden Funktionen gewundert:

foo 5 = 6

foo True = False

beide die obige Typsignatur erfüllen, warum behaupten dann die Haskell-Leute, es sei id allein, die die Typsignatur erfüllt?

Das liegt daran, dass es eine implizite forall in der Typsignatur versteckt. Der eigentliche Typ ist:

id :: forall a. a -> a

Kommen wir also zurück zu der Aussage: Zwänge befreien, Freiheiten schränken ein

Überträgt man dies auf das Typensystem, wird diese Aussage zu:

Eine Einschränkung auf der Ebene des Typs wird zu einer Freiheit auf der Ebene des Begriffs

et

Eine Freiheit auf der Ebene des Typs wird zu einer Einschränkung auf der Ebene des Begriffs

---

Betrachten wir nun die erste Anweisung mit der foo Funktion:

Eine Einschränkung auf der Ebene des Typs..

Wenn wir also eine Einschränkung auf unsere Typsignatur anwenden

foo :: (Num a) => a -> a

wird zu einer Freiheit auf der Ebene des Begriffs gibt uns die Freiheit oder Flexibilität, all diese Dinge zu schreiben

foo 5 = 6
foo 4 = 2
foo 7 = 9
...

Das Gleiche lässt sich beobachten, wenn man die folgenden Einschränkungen vornimmt a mit jeder anderen Typklasse usw.

Also, was diese Art von Signatur: foo :: (Num a) => a -> a bedeutet übersetzt soviel wie:

a , st a -> a, a  Num

Dies wird als existentielle Quantifizierung bezeichnet, was übersetzt bedeutet gibt es einige Instanzen von a für die eine Funktion, wenn sie mit etwas vom Typ a gibt etwas vom gleichen Typ zurück, und diese Instanzen gehören alle zu der Menge von Numbers.

Daher können wir sehen, dass das Hinzufügen einer Bedingung (dass a zur Menge der Zahlen gehören sollte), ermöglicht es der Begriffsebene, mehrere mögliche Implementierungen zu haben.

---

Kommen wir nun zur zweiten Aussage, die eigentlich die Erklärung von forall :

Eine Freiheit auf der Ebene des Typs wird zu einer Einschränkung auf der Ebene des Begriffs

Lassen Sie uns nun die Funktion auf der Ebene des Typs befreien:

foo :: forall a. a -> a

Dies bedeutet Folgendes:

a , a -> a

was bedeutet, dass die Implementierung dieser Typsignatur so sein sollte, dass sie a -> a für alle Umstände.

Dies führt dazu, dass wir nun auf der Ebene der Begriffe eingeschränkt werden. Wir können nicht mehr schreiben

foo 5 = 7

denn diese Implementierung würde nicht genügen, wenn wir die a als Bool . a kann ein Char oder eine [Char] oder einen benutzerdefinierten Datentyp. Unter allen Umständen sollte er etwas vom gleichen Typ zurückgeben. Diese Freiheit auf der Ebene des Typs wird als universelle Quantifizierung bezeichnet, und die einzige Funktion, die dies erfüllen kann, ist

foo a = a

die gemeinhin als die identity Funktion

---

Daher forall ist eine liberty auf der Typenebene, deren eigentlicher Zweck es ist constrain die Begriffsebene zu einer bestimmten Implementierung.

Answer 5

Der Grund für die unterschiedlichen Verwendungen dieses Schlüsselworts ist, dass es in mindestens zwei verschiedenen Erweiterungen des Typsystems verwendet wird: Typen höheren Ranges und Existenziale.

Es ist wahrscheinlich am besten, diese beiden Dinge getrennt zu lesen und zu verstehen, anstatt zu versuchen, eine Erklärung dafür zu bekommen, warum "forall" in beiden gleichzeitig ein geeignetes Stück Syntax ist.