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

https://stackoverflow.com/questions/3071136

28-09-2019
|

Frage

Ich fange an zu verstehen, wie das forall Schlüsselwort in so genannten „existentiellen Typen“ wie folgt verwendet wird:

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

Dies ist nur ein Teil, aber wie forall verwendet wird, und ich kann einfach nicht wickeln meinen Gedanken um seine Verwendung in Dinge wie diese:

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

oder zu erklären, warum diese sind anders:

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

oder die gesamte RankNTypes stuff ...

neige ich dazu, klar, Jargon frei Englisch statt der Art der Sprache bevorzugen, die in akademischen Umgebungen normal sind. Die meisten der Erklärungen ich auf, dies zu lesen versuchen (die, die ich über Suchmaschinen finden) haben diese Probleme:

Sie sind unvollständig. Sie erklären, einen Teil der Verwendung dieses Schlüsselwort (wie „existentielle Typen“), die mich glücklich fühlen, bis ich Code gelesen, dass Verwendungen es in eine ganz andere Art und Weise (wie runST, foo und bar oben).
Sie sind dicht mit Annahmen gepackt, dass ich die letzten in welchem ??Zweig der diskreten Mathematik gelesen habe, Kategorientheorie oder die abstrakten Algebra ist in dieser Woche beliebt. (Wenn ich nie die Worte lesen „konsultieren Sie das Papier was für Details der Implementierung“ wieder, wird es zu früh.)
Sie sind in einer Weise geschrieben, dass häufig auch einfache Konzepte verwandeln sich in quälend verdreht und gebrochen Grammatik und Semantik.

So ...

Auf die eigentliche Frage. Kann jemand vollständig forall Schlüsselwort in einer klaren, einfachem Englisch erklären (oder, wenn es irgendwo, zeigen Sie auf eine solche eindeutige Erklärung gibt, die ich verpasst habe), dass ich ein Mathematiker tränkt nicht davon ausgehen, im Jargon bin?

Edited hinzufügen:

Es waren zwei Stand-out Antworten von den höherwertigen, die unten, aber leider kann ich nur ein, wie am besten wählen. Norman Antwort wurde ausführlich und nützlich , Dinge zu erklären in einer Weise, dass einige der theoretischen Grundlagen von forall und zugleich zeigt mir einige der praktischen Auswirkungen zeigte. yairchu Antwort eine Fläche niemand bedeckt sonst (Variablen scoped Typ) genannt und alle Konzepte mit Code und einer GHCi Sitzung dargestellt. Wäre es möglich, sowohl als beste zu wählen, würde ich. Leider kann ich nicht, und nach eng beiden Antworten suchen über, habe ich entschieden, dass yairchu leicht wegen des anschaulichen Code und die angeschlossenen Erklärung heraus Norman ist Kante. Das ist ein bisschen unfair, aber, weil ich wirklich beiden Antworten benötigt, um dies auf den Punkt zu verstehen, dass forall ist Verlass mich nicht mit einem schwachen Gefühl der Angst, wenn ich es in einer Art Unterschrift sehen.

Lösung

Beginnen wir mit einem Codebeispiel:

foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
foob postProcess onNothin onJust mval =
    postProcess val
    where
        val :: b
        val = maybe onNothin onJust mval

Mit diesem Code lässt sich nicht kompilieren (Syntaxfehler) im Klar Haskell 98. eine Erweiterung erfordert die forall Schlüsselwort zu unterstützen.

Grundsätzlich gibt es 3 verschiedene gemeinsame Verwendungen für das forall Schlüsselwort (oder zumindest so es scheint ), und jeder hat seine eigene Haskell-Erweiterung: ScopedTypeVariables, RankNTypes / Rank2Types, ExistentialQuantification.

Der obige Code wird nicht einen Syntaxfehler mit einem diesem aktiviert, aber nur geben Kontrollen mit ScopedTypeVariables aktiviert.

Scoped Typ Variablen:

Scoped Typ Variablen hilft einem Typen für Code innerhalb where Klauseln angeben. Es macht die b in val :: b das gleiche wie das b in foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Ein verwirrender Punkt : Sie können hören, dass, wenn Sie die forall von einem Typ auslassen es tatsächlich noch implizit vorhanden ist. ( von Normans Antwort: „normalerweise diese Sprachen auslassen die forall von polymorphen Typen "). Diese Behauptung ist richtig, und es bezieht sich auf die anderen Verwendungen von forall, und nicht auf die ScopedTypeVariables Verwendung.

Rank-N-Typen:

Beginnen wir mit diesem mayb :: b -> (a -> b) -> Maybe a -> b entspricht mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, außer für wenn ScopedTypeVariables aktiviert ist.

Das bedeutet, dass es für jeden a und b funktioniert.

Lassen Sie uns sagen wollen Sie so etwas wie dies zu tun.

ghci> let putInList x = [x]
ghci> liftTup putInList (5, "Blah")
([5], ["Blah"])

Was der Typ dieses liftTup sein muss? Es ist liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Um zu sehen, warum sie zum Code versucht es:

ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b)
ghci> liftTup (\x -> [x]) (5, "Hello")
    No instance for (Num [Char])
    ...
ghci> -- huh?
ghci> :t liftTup
liftTup :: (t -> t1) -> (t, t) -> (t1, t1)

„Hmm .. warum GHC daraus schließen, dass das Tupel zwei des gleichen Typs enthalten? Lassen Sie uns sagen, dass es sie müssen nicht sein“

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

Hmm. so hier nicht GHC nicht lassen Sie uns liftFunc auf v anzuwenden, weil v :: b und liftFunc eine x will. Wir wollen wirklich unsere Funktion, eine Funktion zu erhalten, die eine mögliche x akzeptiert!

{-# LANGUAGE RankNTypes #-}
liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

So ist es nicht, das funktioniert für alle liftTup x, dann ist es die Funktion, dass es kommt, dass der Fall ist.

Existentielle Quantifizierung:

Lassen Sie uns die Verwendung ein Beispiel:

-- test.hs
{-# LANGUAGE ExistentialQuantification #-}
data EQList = forall a. EQList [a]
eqListLen :: EQList -> Int
eqListLen (EQList x) = length x

ghci> :l test.hs
ghci> eqListLen $ EQList ["Hello", "World"]
2

Wie ist das anders als Rank-N-Typen?

ghci> :set -XRankNTypes
ghci> length (["Hello", "World"] :: forall a. [a])
    Couldnt match expected type 'a' against inferred type '[Char]'
    ...

Mit Rang-N-Typen, forall a bedeutete, dass Ihr Ausdruck alle möglichen as passen. Zum Beispiel:

ghci> length ([] :: forall a. [a])
0

Eine leere Liste funktioniert als eine Liste aller Art.

So mit Existentielle-Quantifizierung, foralls in data Definitionen bedeutet, dass enthielt der Wert kann sein jeder geeigneten Art, nicht, dass es muss sein alle geeignete Typen.

Andere Tipps

Kann jemand vollständig erklärt das forall Stichwort in klaren, einfachem Englisch?

Nein. (Na ja, vielleicht Don Stewart kann.)

Hier sind die Hindernisse für eine einfache, klare Erklärung oder forall:

Es ist ein Quantor. Sie haben eine zumindest haben ein wenig Logik (Prädikat Kalkül) einen universellen oder Existenzquantor gesehen zu haben. Wenn Sie noch nie Prädikat Kalkül gesehen haben oder sind nicht zufrieden mit quantifiers (und ich habe Studenten während PhD Qualifikationsprüfungen gesehen, die nicht bequem sind), dann für Sie, es gibt keine einfache Erklärung forall.
Es ist ein type quantifier. Wenn Sie nicht System F und bekommen einige Übung Schreiben polymorphe Typen gesehen haben, Sie gehen zu finden forall verwirrend. Die Erfahrungen mit Haskell oder ML ist nicht genug, denn normalerweise werden diese Sprachen die forall von polymorphen Typen auslassen. (In meinem Kopf, das ist eine Sprache-Design Fehler.)
In Haskell insbesondere forall wird in einer Weise verwendet, dass ich verwirrend finden. (Ich bin kein Typ Theoretiker, aber meine Arbeit bringt mich in Kontakt mit einem Los vom Typ Theorie, und ich bin sehr zufrieden mit ihm.) Für mich ist die wichtigste Quelle der Verwirrung ist, dass forall wird verwendet, um eine Art zu codieren, dass ich selbst würde mit exists schreiben bevorzugen. Es ist von einem kniffligen Bit vom Typ Isomorphismus gerechtfertigt quantifiers und Pfeile beteiligt, und jedes Mal, wenn ich es verstehen will, muß ich Dinge nachzuschlagen und Arbeit aus dem Isomorphismus selbst.

Wenn Sie sich nicht wohl mit der Idee vom Typ Isomorphismus sind, oder wenn Sie haben keine Praxis Denken über Art Isomorphismen, diese Verwendung von forall wird Sie stymie.
Während das allgemeine Konzept des forall ist immer das gleiche (Binde eine Variable vom Typ einzuführen), können die Details von verschiedenen Anwendungen erheblich variieren. Informelle Englisch ist nicht ein sehr gutes Werkzeug, um die Variationen zu erläutern. Um wirklich zu verstehen, was los ist, müssen Sie einige Mathematik. In diesem Fall kann die relevante Mathematik in Benjamin Pierce einleitenden Text Typen und Programmiersprachen , das ein sehr gutes Buch gefunden werden.

Wie für Ihre speziellen Beispiele,

runST sollte machen Sie Ihren Kopf verletzt. Höherrangigen Typen (forall links von einem Pfeil) sind selten in der Wildnis gefunden. Ich ermutige Sie, um das Papier zu lesen, dass runST eingeführt: "Faule Funktionszustand Threads" . Dies ist ein wirklich gutes Papier, und es wird Ihnen ein viel besseres Gespür für die Art von runST im Besonderen und für höherrangige Arten im Allgemeinen geben. Die Erklärung nimmt mehrere Seiten, wird es sehr gut gemacht, und ich werde nicht versuchen, es hier zu kondensieren.
Betrachten
```
foo :: (forall a. a -> a) -> (Char,Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))
```
Wenn ich bar nennen, kann ich einfach jede Art a wählen, dass Ich mag, und ich kann es eine Funktion vom Typ a zu Typ a passieren. Zum Beispiel kann ich die Funktion (+1) oder die Funktion reverse passieren. Sie können von der forall denken als zu sagen „Ich werde jetzt den Typ holen“. (Das technische Wort den Typ für die Kommissionierung ist instanziierenden ).

Die Beschränkungen für foo Aufruf sind viel strenger: das Argument foo muss eine polymorphe Funktion sein. Mit dieser Art kann die einzigen Funktionen, die ich zu foo passieren sind id oder eine Funktion, die immer divergiert oder Fehler, wie undefined. Der Grund dafür ist, dass mit foo, die forall nach links des Pfeil ist, so wie der Anrufer von foo ich es nicht zu holen, was a ist-vielmehr ist die Implementierung von foo, die zu holen bekommen, was a ist. Da forall nach links dem Pfeil ist, anstatt über dem Pfeil wie in bar, die Instanziierung im Körper der Funktion und nicht an der Aufrufstelle nimmt.

Zusammenfassung: A vollständig Erklärung des forall Schlüsselwort erfordert Mathe und kann nur von jemandem verstanden werden, die die Mathematik studiert hat. Auch teilweise Erklärungen sind schwer ohne Mathematik zu verstehen. Aber vielleicht meine teilweise, nicht-mathematischen Erklärungen ein wenig helfen. Go lesen Launchbury und Peyton Jones auf runST!

Nachtrag: Jargon "oben", "unten", "links von". Diese haben nichts zu tun mit der Text Möglichkeiten Typen geschrieben und alles mit abstrakten-Syntaxbäume zu tun. In der abstrakten Syntax, nimmt ein forall den Namen einer Variable vom Typ, und dann gibt es eine volle Art „unterhalb“ der forall. Ein Pfeil nimmt zwei Typen (Argument und Ergebnistyp) und bildet einen neuen Typ (der Funktionstyp). Das Argument Typ „links von“ der Pfeil; es ist der linke Kind Pfeil in dem abstrakten-Syntaxbaum.

Beispiele:

In forall a . [a] -> [a] ist die forall über dem Pfeil; was ist auf der linken Seite des Pfeils ist [a].
In
```
forall n f e x . (forall e x . n e x -> f -> Fact x f) 
              -> Block n e x -> f -> Fact x f
```
der Typ in Klammern würde „ein forall links von einem Pfeil“ bezeichnet werden. (Ich verwende Typen wie dies in einem Optimierer ich arbeite.)

Meine ursprüngliche Antwort:

Kann jemand vollständig forall Schlüsselwort in klar erklären, plain English

Wie Norman sagt, es ist sehr schwer, eine klare, einfache englische Erklärung zu geben, eines technischen Begriff von Typentheorie. Wir alle versuchen, though.

Es gibt wirklich nur eine Sache, über ‚forall‘ zu erinnern: es bindet Typen ein gewisser Spielraum . Sobald Sie das verstehen, ist alles ziemlich einfach. Es ist der äquivalent ‚lambda‘ (oder eine Form von ‚lassen‘) auf der Typebene - Norman Ramsey in sein ausgezeichnete Antwort .

Die meisten Anwendungen von ‚forall‘ sind sehr einfach, und Sie können sie eingeführt in die GHC Benutzerhandbuch, S7.8 ., Insbesondere die ausgezeichnete S7.8.5 auf verschachtelte Formen des 'forall'.

In Haskell, wir in der Regel aus dem Bindemittel lassen Typen, wenn der Typ ist universell quanitified, etwa so:

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

entspricht:

length :: [a] -> Int

Das ist es.

Da Sie Variablen vom Typ nun bis zu einem gewissen Umfang binden können, können Sie Bereiche haben andere der obersten Ebene als ( " allquantifizierte "), wie Ihr erstes Beispiel, wobei der Typ Variable ist nur sichtbar innerhalb der Datenstruktur. Dies erlaubt für versteckte Typen ( " existentielle Typen "). Oder wir können haben willkürliche Verschachtelung von Bindungen ( "Rang N-Typen").

Um tief Typ Systeme verstehen, müssen Sie einige Jargon lernen. das ist, die Art der Informatik. Allerdings sollten einfache Anwendungen, wie oben, sein Lage über Analogie gegriffen werden kann intuitiv mit ‚lassen‘ auf der Werteebene. EIN großartige Einführung ist Launchbury und Peyton Jones .

Sie sind dicht mit Annahmen gepackt, dass ich die letzten in welchem ??Zweig der diskreten Mathematik gelesen habe, Kategorientheorie oder die abstrakten Algebra ist in dieser Woche beliebt. (Wenn ich nie die Worte lesen „konsultieren Sie das Papier, was für Einzelheiten der Umsetzung“ wieder, wird es zu früh.)

Er, und was über einfache Logik erster Ordnung? forall ist ziemlich eindeutig in Bezug auf Allquantifizierung , und in diesem Zusammenhang der Begriff existentielle macht auch mehr Sinn, obwohl es weniger umständlich wäre, wenn es ein exists Schlüsselwort ist. Quantifizierung Ob effektiv Universal- oder existentielle hängt von der Platzierung des Quantors relativ zu denen die Variablen, auf welcher Seite einer Funktion Pfeil verwendet werden, und es ist alles ein wenig verwirrend.

Also, wenn das nicht hilft, oder wenn Sie einfach nicht wie symbolische Logik, von einer funktionalen Programmierung-ish Perspektive Sie von Typ-Variablen denken können als nur sein (implizite) type Parameter an die Funktion. Funktionen Typ Parameter in diesem Sinne genommen werden eine Kapital Lambda mit welchen Gründen auch immer traditionell geschrieben, die ich hier als /\ schreiben würde.

So, betrachten die id Funktion:

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

Wir können es als Lambda-Ausdrücke umschreiben, Bewegen die „Typ-Parameter“ aus der Art Signatur und das Hinzufügen von Inline-Anmerkungen:

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

Hier ist die gleiche Sache zu const getan:

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

So Ihre bar Funktion so etwas wie das sein könnte:

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

Beachten Sie, dass die Art der Funktion bar als Argument angegeben, hängt von bar des Typparameter. Erwägen Sie, wenn Sie hatte so etwas wie dieses stattdessen:

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

Hier bar2 ist die Funktion etwas vom Typ Char Anwendung, so geben bar2 jede Art andere Parameter als Char einen Typfehler verursacht.

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

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

Im Gegensatz zu bar, hat foo nicht wirklich nehmen alle Parameter des Typs überhaupt! Es dauert eine Funktion, die selbst einen Typparameter nimmt, dann gilt diese Funktion auf zwei andere Typen.

Wenn Sie also eine forall in einer Art Unterschrift sehen, man denke nur an sie als Lambda-Ausdruck für Typ Signaturen . Genau wie regelmäßige lambdas erstreckt sich der Umfang der forall so weit nach rechts wie möglich, bis zu umschließende Klammer, und genau wie Variablen in einem regelmäßigen Lambda gebunden, gebunden die Typvariablen von einem forall sind nur in ihrem Umfang innerhalb des quantifizierten Ausdrucks.

Post scriptum : Vielleicht fragen Sie sich vielleicht - jetzt, dass wir denken über Funktionen Typ Parameter nehmen, warum können wir nicht tun etwas interessanter mit diesen Parametern als steckte sie in eine Art Unterschrift ? Die Antwort ist, dass wir können!

Eine Funktion, die Puts Variablen zusammen mit einem Etikett eingeben und gibt einen neuen Typ ist ein Typkonstruktor , die Sie so etwas schreiben könnte:

Either = /\a b -> ...

Aber wir würden ganz neue Notation müssen, weil die Art und Weise eine solche Art geschrieben ist, wie Either a b, ist bereits andeutend „gelten die Funktion Either auf diese Parameter“.

Auf der anderen Seite, eine Funktion, die eine Art „Musterübereinstimmungen“ auf seiner Art Parametern, verschiedene Werte für verschiedene Arten der Rückkehr ist eine Methode einer Typklasse . Eine leichte Erweiterung meiner /\ Syntax über so etwas wie dies schon sagt:

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 denke, ich Haskell tatsächlichen syn bevorzugenSteuer ...

Eine Funktion, die "-Muster matches" seine Art Parameter und gibt eine beliebige, bestehende Typ ist ein type Familie oder funktionale Abhängigkeit - im ersteren Fall ist es sogar sieht schon viel wie eine Funktionsdefinition.

Hier ist eine schnelle und schmutzige Erklärung in einfachen Worten, dass Sie wahrscheinlich bereits vertraut sein.

Das forall Schlüsselwort ist wirklich nur in einer Art und Weise in Haskell verwendet. Es bedeutet immer die gleiche Sache, wenn Sie es sehen.

Universal Quantifizierung

A allquantifizierte Typ ist eine Art von Form forall a. f a. Der Wert dieser Art kann wie folgt beschrieben werden eine Funktion , die einen Typen a als Argument und gibt einen Wert vom Typ f a nimmt. Außer, dass in Haskell diese Art Argumente implizit vom Typ System übergeben werden. Diese „Funktion“ hat man den gleichen Wert, egal zu geben, welche Art sie erhält, so ist der Wert polymorphe .

Betrachten wir zum Beispiel den Typ forall a. [a]. Der Wert dieser Art nimmt einen anderen Typ a und gibt Ihnen eine Liste von Elementen des gleichen Typs a zurück. Es gibt nur eine mögliche Implementierung, natürlich. Es würde haben Sie die leere Liste zu geben, weil a absolut jede Art sein könnte. Die leere Liste ist der einzige Liste Wert, der in seinem Elementtyp polymorph ist (da es keine Elemente hat).

oder die Art forall a. a -> a. Der Anrufer einer solchen Funktion bietet sowohl eine Art a und einen Wert vom Typ a. Die Umsetzung hat dann einen Wert des gleichen Typs a zurückzukehren. Es gibt nur eine mögliche Implementierung wieder. Es würde den gleichen Wert zurück, dass es gegeben wurde.

Existentielle Quantifizierung

Ein existenzquantifizierte Typ würde die Form exists a. f a haben, wenn Haskell, dass die Schreibweise unterstützt. Ein Wert dieses Typs kann wie folgt beschrieben werden ein Paar (oder ein „Produkt“), bestehend aus einem Typ a und einen Wert vom Typ f a.

Zum Beispiel, wenn Sie einen Wert vom Typ exists a. [a] haben, haben Sie eine Liste von Elementen eines bestimmten Typs. Es könnte jede Art sein, aber selbst wenn Sie nicht wissen, was es ist, es gibt eine Menge zu eine solche Liste tun könnte. Man könnte es umgekehrt, oder Sie können die Anzahl der Elemente, oder führen Sie eine beliebige andere Listenoperation zählen, die nicht von der Art des Elements abhängt.

OK, also warten Sie eine Minute. Warum forall Haskell Verwendung einen „existenziellen“ Typen wie die folgenden bezeichnen?

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

Es kann verwirrend sein, aber es ist wirklich die Beschreibung des Typ des Datums Konstruktor SB:

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

Sobald konstruiert, können Sie von einem Wert des Typs ShowBox denken als von zwei Dingen besteht. Es ist eine Art s zusammen mit einem Wert vom Typ s. Mit anderen Worten, es ist ein Wert eines existentiell quantifiziert Typ. ShowBox könnte wirklich als exists s. Show s => s geschrieben werden, wenn Haskell diese Schreibweise unterstützt.

runST und Freunde

Da, wie sind diese anders?

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

Lassen Sie uns zunächst take bar. Es dauert eine Art a und eine Funktion vom Typ a -> a und erzeugt einen Wert vom Typ (Char, Bool). Wir konnten Int als a wählen und geben ihm eine Funktion vom Typ Int -> Int zum Beispiel. Aber foo ist anders. Es setzt voraus, dass die Umsetzung der foo der Lage sein, jede Art zu übergeben es an die Funktion will wir es geben. So ist die einzige Funktion konnten wir vernünftigerweise geben id ist.

Wir sollten nun in der Lage sein, die Bedeutung der Art der runST zu bewältigen:

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

So runST muss in der Lage einen Wert vom Typ a zu produzieren, egal was geben wir als a geben. Dazu braucht es ein Argument vom Typ forall s. ST s a, die unter der Haube nur eine Funktion vom Typ forall s. s -> (a, s) ist. Diese Funktion dann ganz gleich einen Wert vom Typ (a, s) zu produzieren in der Lage sein, was die Umsetzung der runST Typ entscheidet als s zu geben.

OK, so was? Der Vorteil ist, dass diese auf dem Anrufer von runST in einer Bedingung stellt, dass der Typ a können den Typ s überhaupt nicht beteiligt. Sie können es nicht einen Wert vom Typ ST s [s] passieren, zum Beispiel. Was das bedeutet in der Praxis, dass die Umsetzung von runST frei Mutation mit dem Wert vom Typ s auszuführen. Das Typ-System garantiert, dass diese Mutation auf die Umsetzung der runST lokal ist.

Die Art der runST ist ein Beispiel für eine Rang-2 polymorphen Typ , da der Typ des Arguments enthält eine forall quantifier. Die Art der foo oben ist auch von Rang 2. Ein gewöhnlicher polymorphe Art, wie die von bar, ist Rang-1, aber es wird Rang-2, wenn die Typen von Argumenten polymorphen sein müssen, mit ihren eigenen forall quantifier. Und wenn eine Funktion Rang-2 Argumente nimmt dann seine Art ist Rang-3, und so weiter. Im Allgemeinen ist eine Art, die polymorphe Argumente von Rang n nimmt hat Rang n + 1.

Der Grund, warum gibt es verschiedene Verwendungen dieses Schlüsselwort ist, dass es tatsächlich in mindestens zwei verschiedenen Typen Systemerweiterungen verwendet wird. Höherrangigen Typen und Existenziale

Es ist wahrscheinlich am besten, nur um zu lesen und diese beiden Dinge getrennt zu verstehen, anstatt zu versuchen, eine Erklärung dafür zu bekommen, warum forall 'ist eine geeignete Bit-Syntax in beide zur gleichen Zeit.

Kann jemand vollständig forall Stichwort in klaren, einfachem Englisch erklären (oder, falls es irgendwo existiert, zeigen Sie auf eine solche klare Erklärung, die ich verpasst habe), die nicht davon ausgehen, ich bin ein Mathematiker im Jargon durchdrungen?

Ich werde nur die Bedeutung zu erklären versuchen und vielleicht die Anwendung von forall im Zusammenhang mit Haskell und seinen Art-Systemen.

Aber bevor Sie verstehen, dass ich Ihnen zu schreiben möchte sehr zugänglich und nettes Gespräch von Runar Bjarnason dem Titel „ Constraints Liberate, Freiheiten Constrain ". Die Rede ist voll von Beispielen aus der realen Welt Use Cases sowie Beispiele in Scala diese Erklärung zu unterstützen, obwohl es nicht forall nicht erwähnt. Ich werde versuchen, die forall Perspektive unten zu erklären.

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Es ist sehr wichtig, zu verdauen und zu glauben, dass diese Aussage mit der folgenden Erklärung zu gehen, so dass ich Sie bitten, das Gespräch zu sehen (zumindest Teilen davon).

Nun wird ein sehr häufiges Beispiel, die Ausdruckskraft des Typs System Haskell zeigt diese Art Signatur:

foo :: a -> a

Es wird gesagt, dass diese Art Unterschrift gegeben, gibt es nur eine Funktion, die diese Art erfüllen kann und das ist die identity Funktion oder was ist besser bekannt bekannt id.

In der Anfangsphase von mir lernen Haskell, habe ich immer die folgenden Funktionen gewundert:

foo 5 = 6

foo True = False

Sie erfüllen sowohl die oben genannte Art Unterschrift, dann warum Leute Haskell behaupten, dass es id allein das genügt der Typ Signatur?

Das ist, weil es eine implizite forall in der Art Signatur versteckt ist. Der tatsächliche Typ ist:

id :: forall a. a -> a

Jetzt Also, lassen Sie uns wieder zu der Aussage: Einschränkungen befreien, Freiheiten constrain

Translating, dass auf die Art System, diese Aussage wird:

Eine Beschränkung auf der Typebene, eine Freiheit auf dem Begriff Ebene wird

und

Eine Freiheit auf der Typebene, eine Einschränkung auf dem Begriff Ebene wird

Lassen Sie uns versuchen, die erste Aussage zu beweisen:

Eine Beschränkung auf der Typebene ..

So eine Einschränkung für unsere Art Unterschrift setzen

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

wird eine Freiheit auf dem Begriff Ebene gibt uns die Freiheit oder Flexibilität alle diese

zu schreiben

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

Das gleiche kann durch Zwang a mit jedem anderen typeclass etc

beobachtet werden

Was also jetzt diese Art Unterschrift: foo :: (Num a) => a -> a übersetzt ist:

∃a , st a -> a, ∀a ∈ Num

Dies ist als existentielle Quantifizierung bekannt, was übersetzt existiert einige Fälle von a, für die eine Funktion, wenn etwas vom Typ a kehrt etwas von der gleichen Art zugeführt, und diese Instanzen alle gehören in die Satz von Zahlen.

Wir können also eine Einschränkung sehen Zugabe (das a zu dem Satz von Zahlen gehören soll), setzt den Begriff Ebene mehr möglichen Implementierungen zu haben.

Nun zur zweiten Aussage kommen und die, die tatsächlich die Erklärung von forall trägt:

Eine Freiheit auf der Typebene, wird eine Einschränkung auf dem Begriff Ebene

So, jetzt lassen Sie uns die die Funktion auf der Typebene befreien:

foo :: forall a. a -> a

Nun bedeutet dies an:

∀a , a -> a

Das bedeutet, dass die Durchführung dieser Art Signatur sollte so sein, dass es a -> a für alle Umstände ist.

So, jetzt beginnt das uns auf dem Begriff Ebene einzuschränken. Wir können nicht mehr schreiben

foo 5 = 7

, weil diese Implementierung nicht erfüllen würde, wenn wir a als Bool setzen. a kann ein Char oder ein [Char] seinoder ein benutzerdefinierter Datentyp. Unter allen Umständen sollte es etwas vom ähnlichen Typ zurückzukehren. Diese Freiheit auf der Typebene ist das, was als Universal-Quantifizierung bekannt ist und die einzige Funktion, die diese erfüllen kann, ist

foo a = a

, die gemeinhin als die identity Funktion bekannt ist,

Daher forall ist ein liberty auf der Typebene, deren eigentlicher Zweck ist es, den Begriff Ebene auf eine bestimmte Implementierung constrain.

Wie ist existentiell existentielle?

Mit Existentielle-Quantifizierung, foralls in data Definitionen bedeutet dass enthielt der Wert kann sein jeder geeigneten Art, nicht dass es muss sein alle geeigneter Typen. - yachiru Antwort

Eine Erklärung, warum forall in data Definitionen sind isomorph (exists a. a) (pseudo-Haskell) in wikibooks des "Haskell / existenzquantifizierte Arten" .

Es folgt eine kurze Zusammenfassung wörtlich:

data T = forall a. MkT a -- an existential datatype
MkT :: forall a. a -> T -- the type of the existential constructor

Wenn Pattern-Matching / Dekonstruktion MkT x, was ist die Art von x?

foo (MkT x) = ... -- -- what is the type of x?

x kann jede Art sein (wie in den forall angegeben), und so seine Art ist:

x :: exists a. a -- (pseudo-Haskell)

Daher ist die folgende isomorph sind:

data T = forall a. MkT a -- an existential datatype
data T = MkT (exists a. a) -- (pseudo-Haskell)

forall bedeutet forall

Meine einfache Interpretation von alledem ist, dass „forall wirklich bedeutet‚für alle‘“. Eine wichtige Unterscheidung zu machen, ist die Wirkung von forall auf der Seite Definition im Vergleich Funktion Anwendung .

Ein forall bedeutet die Definition des Wertes oder Funktion muss polymorph sein.

Wenn das Ding definiert ist, ist eine polymorphe Wert , dann bedeutet es, dass der Wert für alle geeignet a gültig sein muss, die sehr restriktiv ist.

Wenn das Ding definiert ist, eine polymorphe ist Funktion , dann bedeutet es, dass die Funktion für alle geeignet a gültig sein muss, die da einfach nicht so restriktiv ist, weil die Funktion polymorph ist nicht bedeuten, wobei die Parameter angewandt haben polymorph sein. Das heißt, wenn die Funktion für alle a gültig ist, dann umgekehrt jede geeignet a angewendet werden , um die Funktion. Jedoch kann der Typ des Parameters nur einmal in der Funktionsdefinition gewählt werden.

Wenn ein forall ist innerhalb des Typs des Funktionsparameters (dh ein Rank2Type), dann bedeutet es, die angewandt Parameter muss seine wirklich polymorphe, um im Einklang mit der Idee forall Mittel Definition ist polymorph. In diesem Fall kann die Art des Parameters gewählt wird, mehr als einmal in der Funktionsdefinition ( "und wird durch die Implementierung der Funktion gewählt, “wie von Norman )

Daher ist der Grund, warum existentielle data Definitionen erlaubt jede a ist, weil die Daten Konstruktor ist eine polymorphe Funktion :

MkT :: forall a. a -> T

Art von MKT :: a -> *

Welche jede a Mittel können auf die Funktion angewendet werden. Im Gegensatz zu, sagen wir, eine polymorphe Wert :

valueT :: forall a. [a]

Art Wertt :: a

Das bedeutet, dass die Definition von Wertt polymorph sein muss. In diesem Fall kann valueT als leere Liste [] aller Art definiert werden.

[] :: [t]

Unterschiede

Auch wenn die Bedeutung für forall konsistent ist in ExistentialQuantification und RankNType hat Existenziale einen Unterschied, da der data Konstruktor kann in Musterabgleich verwendet werden. Wie in der ghc Bedienungsanleitung :

Wenn Pattern-Matching, jedes Muster Spiel führt eine neue, eindeutige, geben Sie für jede Existenz Typ Variable. Diese Typen können nicht mit jeder anderen Art vereint werden, noch können sie von dem Umfang des Musters Spiel entkommen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow