Ich fange an zu verstehen, wie das forall
Schlüsselwort in sogenannten "existentiellen Typen" wie diesem verwendet wird:
data ShowBox = forall s. Show s => SB s
Dies ist jedoch nur eine Teilmenge der forall
Verwendung, und ich kann mich einfach nicht auf die Verwendung in solchen Dingen konzentrieren:
runST :: forall a. (forall s. ST s a) -> a
Oder erklären, warum diese unterschiedlich sind:
foo :: (forall a. a -> a) -> (Char, Bool)
bar :: forall a. ((a -> a) -> (Char, Bool))
Oder das ganze RankNTypes
Zeug ...
Ich bevorzuge klares, jargonfreies Englisch gegenüber den im akademischen Umfeld normalen Sprachen. Die meisten Erklärungen, die ich dazu zu lesen versuche (diejenigen, die ich über Suchmaschinen finden kann), haben folgende 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
undbar
oben). - Sie sind vollgepackt mit Annahmen, dass ich die neuesten Informationen zu den Bereichen diskreter Mathematik, Kategorietheorie oder abstrakter Algebra gelesen habe, die diese Woche beliebt sind. (Wenn ich nie die Worte lesen „konsultieren Sie das Papier , was für Einzelheiten der Umsetzung“ wieder, wird es zu früh.)
- Sie sind so geschrieben, dass selbst einfache Konzepte häufig in gewundene und gebrochene Grammatik und Semantik umgewandelt werden.
So...
Weiter zur eigentlichen Frage. Kann jemand das forall
Schlüsselwort vollständig in klarem, einfachem Englisch erklären (oder, falls es irgendwo existiert, auf eine so klare Erklärung verweisen, die ich verpasst habe), die nicht davon ausgeht, dass ich ein im Fachjargon versierter Mathematiker bin?
Bearbeitet, um hinzuzufügen:
Es gab zwei herausragende Antworten von den höherwertigen unten, aber leider kann ich nur eine als die beste auswählen. Normans Antwort war detailliert und nützlich und erklärte die Dinge auf eine Weise, die einige der theoretischen Grundlagen forall
zeigte und mir gleichzeitig einige der praktischen Implikationen davon zeigte. Yairchus Antwortdeckte einen Bereich ab, den sonst niemand erwähnte (Variablen vom Typ Scoped) und illustrierte alle Konzepte mit Code und einer GHCi-Sitzung. Wäre es möglich, beide als am besten auszuwählen, würde ich. Leider kann ich nicht und nachdem ich beide Antworten genau durchgesehen habe, habe ich beschlossen, dass Yairchus aufgrund des illustrativen Codes und der beigefügten Erklärung die von Norman leicht übertrifft. Dies ist jedoch etwas unfair, da ich wirklich beide Antworten brauchte, um dies bis zu einem Punkt zu verstehen, an dem forall
ich kein leichtes Gefühl der Angst habe, wenn ich es in einer Typensignatur sehe.
Antworten:
Beginnen wir mit einem Codebeispiel:
Dieser Code wird in einfachem Haskell 98 nicht kompiliert (Syntaxfehler). Zur Unterstützung des
forall
Schlüsselworts ist eine Erweiterung erforderlich .Grundsätzlich gibt es 3 verschiedene gemeinsame Verwendungen für das
forall
Schlüsselwort (oder zumindest so dass es scheint ), und jeder hat seine eigene Haskell extension:ScopedTypeVariables
,RankNTypes
/Rank2Types
,ExistentialQuantification
.Der obige Code erhält bei beiden aktivierten keinen Syntaxfehler, sondern nur Typprüfungen bei
ScopedTypeVariables
aktivierten.Gültigkeitsbereichstypvariablen:
Typvariablen mit Gültigkeitsbereich helfen dabei, Typen für Code in
where
Klauseln anzugeben . Es macht dasb
imval :: b
selben wie dasb
infoob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b
.Ein verwirrender Punkt : Sie können hören, dass wenn Sie das
forall
von einem Typ weglassen, es tatsächlich immer noch implizit vorhanden ist. ( aus Normans Antwort: "Normalerweise lassen diese Sprachen das Forall von polymorphen Typen weg" ). Diese Behauptung ist richtig, aber es bezieht sich auf die anderen Verwendungen vonforall
, und nicht auf dieScopedTypeVariables
Verwendung.Rang-N-Typen:
Beginnen wir damit,
mayb :: b -> (a -> b) -> Maybe a -> b
was äquivalent zu istmayb :: forall a b. b -> (a -> b) -> Maybe a -> b
, außer wennScopedTypeVariables
aktiviert ist.Dies bedeutet, dass es für alle
a
und funktioniertb
.Angenommen, Sie möchten so etwas tun.
Was muss die Art davon sein
liftTup
? Es istliftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b)
. Um zu sehen warum, versuchen wir es zu codieren:"Hmm ... warum schließt GHC, dass das Tupel zwei des gleichen Typs enthalten muss? Sagen wir mal, dass sie es nicht sein müssen."
Hmm. so hier nicht GHC lassen Sie uns nicht anwenden
liftFunc
auf ,v
weilv :: b
undliftFunc
eine willx
. Wir möchten wirklich, dass unsere Funktion eine Funktion erhält, die alles Mögliche akzeptiertx
!Es funktioniert also nicht
liftTup
für allex
, sondern für die Funktion, die es erhält.Existenzielle Quantifizierung:
Verwenden wir ein Beispiel:
Wie unterscheidet sich das von Rang-N-Typen?
Mit Rang-N-Typen
forall a
bedeutet dies, dass Ihr Ausdruck zu allen möglichena
s passen muss . Zum Beispiel:Eine leere Liste funktioniert als Liste eines beliebigen Typs.
Also mit Existentielle-Quantifizierung,
forall
s indata
Definitionen das bedeuten, der Wert enthalten kann der sein , jede geeigneten Art, nicht , dass es muss von seinen allen geeigneten Typen.quelle
ScopedTypeVariables
schlimmer erscheinen als es ist. Wenn Sie den Typb -> (a -> b) -> Maybe a -> b
mit dieser Erweiterung schreiben , entspricht er immer noch genau demforall a b. b -> (a -> b) -> Maybe a -> b
. Wenn Sie jedoch beziehen mögen das gleicheb
(und hat es nicht implizit quantifiziert) dann müssen Sie die explizit quantifizierte Version schreiben. AndernfallsSTV
wäre eine äußerst aufdringliche Erweiterung.ScopedTypeVariables
und ich denke nicht, dass es schlecht ist. Imho, es ist ein sehr hilfreiches Werkzeug für den Programmierprozess und insbesondere für Haskell-Anfänger, und ich bin dankbar, dass es existiert.Nein. (Vielleicht kann Don Stewart das.)
Hier sind die Hindernisse für eine einfache, klare Erklärung oder
forall
:Es ist ein Quantifizierer. Sie müssen mindestens eine kleine Logik (Prädikatenrechnung) haben, um einen universellen oder existenziellen Quantifizierer zu sehen. Wenn Sie noch nie einen Prädikatenkalkül gesehen haben oder mit Quantifizierern nicht vertraut sind (und ich habe Studenten während der Doktorandenprüfungen gesehen, die sich nicht wohl fühlen), dann gibt es für Sie keine einfache Erklärung dafür
forall
.Es ist eine Art quantifier. Wenn Sie System F noch nicht gesehen und einige Übungen zum Schreiben polymorpher Typen erhalten haben, werden Sie
forall
verwirrend sein. Erfahrung mit Haskell oder ML reicht nicht aus, da diese Sprachen normalerweise dieforall
polymorphen Typen weglassen . (In meinen Augen ist dies ein Fehler beim Sprachdesign.)Insbesondere in Haskell
forall
wird es auf eine Weise verwendet, die ich verwirrend finde. (Ich bin kein Typentheoretiker, aber meine Arbeit bringt mich mit viel Typentheorie in Kontakt , und ich bin damit ziemlich vertraut.) Für mich ist die Hauptursache für Verwirrung, dassforall
ein Typ verwendet wird, der diesen Typ codiert Ich selbst würde lieber mit schreibenexists
. Es ist gerechtfertigt durch ein kniffliges Stück Typisomorphismus mit Quantifizierern und Pfeilen, und jedes Mal, wenn ich es verstehen will, muss ich nachschlagen und den Isomorphismus selbst herausarbeiten.Wenn Sie mit der Idee des
forall
Typisomorphismus nicht vertraut sind oder wenn Sie keine Übung haben, über Typisomorphismen nachzudenken, wird diese Verwendung Sie behindern.Während das allgemeine Konzept von
forall
immer dasselbe ist (Bindung zur Einführung einer Typvariablen), können die Details der verschiedenen Verwendungen erheblich variieren. Informelles Englisch ist kein sehr gutes Werkzeug, um die Variationen zu erklären. Um wirklich zu verstehen, was los ist, braucht man etwas Mathematik. In diesem Fall finden Sie die relevante Mathematik in Benjamin Pierces Einführungstext Typen und Programmiersprachen , der ein sehr gutes Buch ist.Was Ihre speziellen Beispiele betrifft,
runST
sollte deinen Kopf verletzen. Höherrangige Typen (ganz links von einem Pfeil) kommen in freier Wildbahn selten vor. Ich ermutige Sie, das folgende Papier zu lesenrunST
: "Lazy Functional State Threads" . Dies ist ein wirklich gutes Papier, und es gibt Ihnen eine viel bessere Intuition für den TyprunST
im Besonderen und für höherrangige Typen im Allgemeinen. Die Erklärung dauert mehrere Seiten, ist sehr gut gemacht und ich werde hier nicht versuchen, sie zu verdichten.Erwägen
Wenn ich anrufe
bar
, kann ich einfach einen beliebigen Typ auswählena
und ihm eine Funktion von Typa
zu Typ übergebena
. Zum Beispiel kann ich die Funktion(+1)
oder die Funktion übergebenreverse
. Sie können sich dasforall
als "Ich darf jetzt den Typ auswählen" vorstellen. (Das technische Wort für die Auswahl des Typs ist instanziierend .)Die Einschränkungen beim Aufrufen
foo
sind viel strenger: Das Argumentfoo
muss eine polymorphe Funktion sein. Mit dieser Art kann die einzigen Funktionen , die ich passieren zufoo
werdenid
oder eine Funktion, die immer divergiert oder Fehler, wieundefined
. Der Grund dafür ist , dass mitfoo
derforall
ist auf der linken Seite des Pfeils, so wie der Aufruferfoo
ich zu nicht holen , wasa
es-ist vielmehr ist die Umsetzung der ,foo
dass zu holen bekommt , wasa
ist. Daforall
sichbar
die Instanziierung links vom Pfeil und nicht wie in über dem Pfeil befindet , erfolgt sie im Hauptteil der Funktion und nicht an der Anrufstelle.Zusammenfassung: Eine vollständige Erklärung des
forall
Schlüsselworts erfordert Mathematik und kann nur von jemandem verstanden werden, der die Mathematik studiert hat. Selbst teilweise Erklärungen sind ohne Mathematik schwer zu verstehen. Aber vielleicht helfen meine teilweisen, nicht mathematischen Erklärungen ein wenig. Lesen Sie Launchbury und Peyton Jones weiterrunST
!Nachtrag: Jargon "oben", "unten", "links von". Diese haben nichts mit der Art und Weise zu tun, wie Typen in Textform geschrieben werden, und alles, was mit Bäumen mit abstrakter Syntax zu tun hat. In der abstrakten Syntax
forall
nimmt a den Namen einer Typvariablen an, und dann gibt es einen vollständigen Typ "unter" dem Forall. Ein Pfeil nimmt zwei Typen (Argument und Ergebnistyp) und bildet einen neuen Typ (den Funktionstyp). Der Argumenttyp ist "links vom" Pfeil. Es ist das linke Kind des Pfeils im abstrakten Syntaxbaum.Beispiele:
In
forall a . [a] -> [a]
befindet sich der Forall über dem Pfeil. Was links vom Pfeil ist, ist[a]
.Im
Der Typ in Klammern wird als "forall links von einem Pfeil" bezeichnet. (Ich verwende solche Typen in einem Optimierer, an dem ich arbeite.)
quelle
forall a . [a] -> [a]
der Forall links vom Pfeil befindet.forall
unter diesen Umständen als effektiv, Linie Lärm. Ich werde mir das Papier ansehen, auf das Sie verlinkt haben (danke auch für den Link!) Und sehen, ob es in meinem Bereich des Verständnisses liegt. Ein großes Lob.exists
es nie implementiert wurde. (Es ist nicht Teil von System F!) In Haskell wird ein Teil von System F implizit gemacht, ist aberforall
eines der Dinge, die nicht vollständig unter den Teppich gekehrt werden können. Es ist, als ob sie mit Hindley-Milner angefangen hätten, wasforall
implizit gemacht werden könnte, und sich dann für ein leistungsfähigeres Typsystem entschieden hätten, was diejenigen von uns verwirrte, die FOLs "forall" und "exist" studierten und dort anhielten.Meine ursprüngliche Antwort:
Wie Norman angibt, ist es sehr schwierig, eine klare englische Erklärung eines Fachbegriffs aus der Typentheorie zu geben. Wir versuchen es alle.
Bei 'forall' ist nur eines wirklich zu beachten: Es bindet Typen an einen bestimmten Bereich . Sobald Sie das verstanden haben, ist alles ziemlich einfach. Es ist das Äquivalent von 'Lambda' (oder einer Form von 'Let') auf Typebene - Norman Ramsey verwendet den Begriff "links" / "oben", um dasselbe Konzept des Geltungsbereichs in seiner ausgezeichneten Antwort zu vermitteln .
Die meisten Anwendungen von 'forall' sind sehr einfach, und Sie finden sie im GHC-Benutzerhandbuch, S7.8 ., Insbesondere das ausgezeichnete S7.8.5 für verschachtelte Formen von 'forall'.
In Haskell lassen wir das Bindemittel normalerweise für Typen weg, wenn der Typ universell quanitifiziert ist, wie folgt:
ist äquivalent zu:
Das ist es.
Da Sie jetzt Typvariablen an einen bestimmten Bereich binden können, können Sie andere Bereiche als die oberste Ebene haben (" universell quantifiziert" ") haben, wie in Ihrem ersten Beispiel, in dem die Typvariable nur innerhalb der Datenstruktur sichtbar ist. Dies ermöglicht versteckte Typen (" existenzielle Typen "). Oder wir können willkürliche Verschachtelungen von Bindungen haben ("Rang N-Typen").
Um Typensysteme genau zu verstehen, müssen Sie etwas Jargon lernen. Das ist die Natur der Informatik. Einfache Verwendungen wie oben sollten jedoch in Analogie zu 'let' auf der Wertebene intuitiv erfasst werden können. Eine gute Einführung ist Launchbury und Peyton Jones .
quelle
length :: forall a. [a] -> Int
ist nicht gleichbedeutend mitlength :: [a] -> Int
wannScopedTypeVariables
aktiviert ist. Wenn das vorhandenforall a.
ist, wirkt es sich auflength
diewhere
Klausel aus (falls vorhanden) und ändert die Bedeutung der darin genannten Typvariablena
.Äh, und was ist mit einfacher Logik erster Ordnung?
forall
ist ziemlich klar in Bezug auf die universelle Quantifizierung , und in diesem Zusammenhang ist der Begriff existenziell auch sinnvoller, obwohl es weniger umständlich wäre, wenn es einexists
Schlüsselwort gäbe . Ob die Quantifizierung effektiv universell oder existenziell ist, hängt von der Platzierung des Quantifizierers in Bezug darauf ab, wo die Variablen auf welcher Seite eines Funktionspfeils verwendet werden, und alles ist etwas verwirrend.Also, wenn das nicht hilft, oder wenn Sie einfach nicht wie symbolische Logik, von einer funktionalen Programmierung-ish Perspektive Sie von Typ - Variablen als nur sein (impliziten) denken können , Typ Parameter an die Funktion. Funktionen, die Typparameter in diesem Sinne verwenden, werden traditionell aus irgendeinem Grund mit einem Großbuchstaben geschrieben, als das ich hier schreiben werde
/\
.Betrachten Sie also die
id
Funktion:Wir können es als Lambdas umschreiben, indem wir den "Typparameter" aus der Typensignatur verschieben und Inline-Typanmerkungen hinzufügen:
Hier ist das Gleiche wie
const
:Ihre
bar
Funktion könnte also ungefähr so aussehen:Beachten Sie, dass der Typ der Funktion, die
bar
als Argument angegeben wird, vombar
Typparameter abhängt . Überlegen Sie, ob Sie stattdessen so etwas hatten:Hier
bar2
wird die Funktion auf etwas vom Typ angewendetChar
, sodass die Angabebar2
eines anderen Typparameters alsChar
einen Typfehler verursacht.Auf der anderen Seite
foo
könnte Folgendes aussehen:Im Gegensatz zu
bar
,foo
nehmen nicht wirklich alle Parameter des Typs überhaupt! Es wird eine Funktion verwendet, die selbst einen Typparameter verwendet, und diese Funktion wird dann auf zwei verschiedene Typen angewendet.Wenn Sie also eine
forall
Typensignatur sehen, stellen Sie sie sich einfach als Lambda-Ausdruck für Typensignaturen vor . Genau wie bei regulären Lambdasforall
erstreckt sich der Geltungsbereich von so weit wie möglich nach rechts, bis hin zur Klammer, und genau wie bei Variablen, die in einem regulären Lambda gebundenforall
sind , sind die durch a gebundenen Typvariablen nur innerhalb des quantifizierten Ausdrucks im Geltungsbereich.Post scriptum : Vielleicht fragen Sie sich - jetzt, wo wir über Funktionen nachdenken, die Typparameter verwenden, warum können wir mit diesen Parametern nichts Interessanteres tun, als sie in eine Typensignatur einzufügen? Die Antwort ist, dass wir können!
Eine Funktion, die Typvariablen mit einer Bezeichnung zusammenfügt und einen neuen Typ zurückgibt, ist ein Typkonstruktor , den Sie wie folgt schreiben können:
Aber wir würden eine völlig neue Notation brauchen, da die Art und Weise, wie ein solcher Typ geschrieben wird
Either a b
, bereits darauf hindeutet, "die Funktion anzuwenden"Either
auf diese Parameter ".Andererseits ist eine Funktion, die in ihren Typparametern eine Art "Musterübereinstimmung" aufweist und unterschiedliche Werte für unterschiedliche Typen zurückgibt, eine Methode einer Typklasse . Eine leichte Erweiterung meiner
/\
obigen Syntax deutet auf Folgendes hin:Persönlich denke ich, ich bevorzuge Haskells tatsächliche Syntax ...
Eine Funktion , die „-Muster matches“ seine Art Parameter und gibt einen beliebigen Typ existiert , ist eine Art Familie oder funktionale Abhängigkeit --in ersteren Fall ist es sogar sieht schon viel wie eine Funktionsdefinition.
quelle
λ
, aber die Unicode-Syntaxerweiterung von GHC unterstützt dies nicht, da λ ein Buchstabe ist , eine unglückliche Tatsache, die hypothetisch auch für meine hypothetischen Big-Lambda-Abstraktionen gelten würde. Daher/\
in Analogie zu\
. Ich nehme an, ich hätte es einfach benutzen können,∀
aber ich habe versucht, Prädikatenrechnung zu vermeiden ...Hier ist eine schnelle und schmutzige Erklärung in einfachen Worten, mit der Sie wahrscheinlich bereits vertraut sind.
Das
forall
Schlüsselwort wird in Haskell wirklich nur auf eine Weise verwendet. Es bedeutet immer dasselbe, wenn Sie es sehen.Universelle Quantifizierung
Ein universell quantifizierter Typ ist ein Typ der Form
forall a. f a
. Ein Wert dieses Typs kann als eine Funktion betrachtet werden , die einen Typa
als Argument verwendet und einen Wert vom Typ zurückgibtf a
. Außer dass diese Typargumente in Haskell implizit vom Typsystem übergeben werden. Diese "Funktion" muss Ihnen unabhängig vom Typ den gleichen Wert geben, daher ist der Wert polymorph .Betrachten Sie zum Beispiel den Typ
forall a. [a]
. Ein Wert dieses Typs nimmt einen anderen Typ ana
und gibt Ihnen eine Liste von Elementen desselben Typs zurücka
. Natürlich gibt es nur eine mögliche Implementierung. Es müsste Ihnen die leere Liste geben, da esa
sich um absolut jeden Typ handeln könnte. Die leere Liste ist der einzige Listenwert, der in seinem Elementtyp polymorph ist (da er keine Elemente enthält).Oder der Typ
forall a. a -> a
. Der Aufrufer einer solchen Funktion gibt sowohl einen Typa
als auch einen Wert vom Typ ana
. Die Implementierung muss dann einen Wert desselben Typs zurückgebena
. Es gibt wieder nur eine mögliche Implementierung. Es müsste den gleichen Wert zurückgeben, den es erhalten hat.Existenzielle Quantifizierung
Ein existenziell quantifizierter Typ hätte die Form
exists a. f a
, wenn Haskell diese Notation unterstützen würde. Ein Wert dieses Typs kann als ein Paar (oder ein "Produkt") betrachtet werden, das aus einem Typa
und einem Wert des Typs bestehtf a
.Wenn Sie beispielsweise einen Wert vom Typ haben
exists a. [a]
, haben Sie eine Liste von Elementen eines Typs. Es könnte jeder Typ sein, aber selbst wenn Sie nicht wissen, was es ist, können Sie mit einer solchen Liste viel anfangen. Sie können es umkehren oder die Anzahl der Elemente zählen oder eine andere Listenoperation ausführen, die nicht vom Typ der Elemente abhängt.OK, also warte eine Minute. Warum bezeichnet Haskell
forall
einen "existenziellen" Typ wie den folgenden?Es kann verwirrend sein, aber es beschreibt wirklich den Typ des Datenkonstruktors
SB
:Einmal konstruiert, können Sie sich einen Wert vom Typ
ShowBox
vorstellen, der aus zwei Dingen besteht. Es ist ein Typs
zusammen mit einem Wert von Typs
. Mit anderen Worten, es ist ein Wert eines existenziell quantifizierten Typs.ShowBox
könnte wirklich so geschrieben werden, alsexists s. Show s => s
ob Haskell diese Notation unterstützt.runST
und FreundeWie unterscheiden sich diese?
Nehmen wir zuerst
bar
. Es nimmt einen Typa
und eine Funktion des Typsa -> a
an und erzeugt einen Wert des Typs(Char, Bool)
. Wir konnten wählen ,Int
als dasa
und geben ihm eine Funktion vom TypInt -> Int
zum Beispiel. Istfoo
aber anders. Es erfordert, dass die Implementierung in derfoo
Lage ist, jeden gewünschten Typ an die von uns zugewiesene Funktion zu übergeben. Die einzige Funktion, die wir vernünftigerweise geben könnten, istid
.Wir sollten jetzt in der Lage sein, die Bedeutung der Art von
runST
:Muss
runST
also in der Lage sein, einen Wert vom Typ zu erzeugena
, egal welchen Typ wir gebena
. Dazu wird ein Argument vom Typ verwendet,forall s. ST s a
das sicherlich irgendwie das erzeugen mussa
. Darüber hinaus muss es in der Lage sein, einen Wert vom Typ zu erzeugen,a
unabhängig davon, für welchen Typ sich die ImplementierungrunST
entscheidets
.In Ordnung und jetzt? Der Vorteil besteht darin, dass dies den Aufrufer dahingehend einschränkt,
runST
dass der Typ den Typa
überhaupt nicht einbeziehen kanns
. Sie können ihm beispielsweise keinen Wert vom Typ übergebenST s [s]
. In der Praxis bedeutet dies, dass die Implementierung vonrunST
frei ist, eine Mutation mit dem Wert des Typs durchzuführens
. Der Typ garantiert, dass diese Mutation lokal für die Implementierung von istrunST
.Der Typ von
runST
ist ein Beispiel für einen polymorphen Typ vom Rang 2, da der Typ seines Arguments einenforall
Quantifizierer enthält . Derfoo
obige Typ hat ebenfalls Rang 2. Ein gewöhnlicher polymorpher Typ wie der vonbar
ist Rang 1, wird jedoch Rang 2, wenn die Argumenttypen polymorph sein müssen, mit einem eigenenforall
Quantifizierer. Und wenn eine Funktion Rang-2-Argumente akzeptiert, ist ihr Typ Rang-3 und so weiter. Im Allgemeinen hat ein Typ, der polymorphe Argumente mit Rang verwendet,n
Rangn + 1
.quelle
Ich werde versuchen, nur die Bedeutung und vielleicht die Anwendung
forall
von Haskell und seinen Typsystemen zu erklären .Aber bevor Sie verstehen, dass ich Sie zu einem sehr zugänglichen und netten Vortrag von Runar Bjarnason mit dem Titel " Constraints Liberate, Liberties Constrain " führen möchte . Der Vortrag ist voll von Beispielen aus realen Anwendungsfällen sowie Beispielen in Scala, um diese Aussage zu unterstützen, obwohl sie nicht erwähnt wird
forall
. Ich werde versuchen, dieforall
Perspektive unten zu erklären .Es ist sehr wichtig, diese Aussage zu verdauen und zu glauben, um mit der folgenden Erklärung fortzufahren. Ich fordere Sie daher dringend auf, das Gespräch (zumindest Teile davon) zu verfolgen.
Ein sehr verbreitetes Beispiel, das die Ausdruckskraft des Haskell-Typsystems zeigt, ist diese Typensignatur:
foo :: a -> a
Es wird gesagt, dass es bei dieser Typensignatur nur eine Funktion gibt, die diesen Typ erfüllen kann, und das ist die
identity
Funktion oder was im Volksmund bekannt istid
.In den Anfangsphasen, in denen ich Haskell lernte, habe ich mich immer gefragt, welche Funktionen es gibt:
beide erfüllen die oben genannte Typensignatur. Warum behaupten dann die Haskell-Leute, dass
id
nur die Typensignatur erfüllt ist?Dies liegt daran, dass
forall
in der Typensignatur ein implizites Element versteckt ist. Der tatsächliche Typ ist:Kommen wir nun zu der Aussage zurück: Einschränkungen befreien sich, Freiheiten beschränken sich
Wenn Sie dies in das Typsystem übersetzen, lautet diese Anweisung:
Eine Einschränkung auf Typebene wird auf der Termebene zur Freiheit
und
Eine Freiheit auf Typebene wird zu einer Einschränkung auf Termebene
Versuchen wir, die erste Aussage zu beweisen:
Eine Einschränkung auf Typebene.
Setzen Sie also eine Einschränkung für unsere Typensignatur
wird eine Freiheit auf der Begriffsebene gibt uns die Freiheit oder Flexibilität, all dies zu schreiben
Gleiches kann beobachtet werden, indem
a
mit jeder anderen Typklasse usw. Eingeschränkt wirdNun bedeutet diese Typensignatur:
foo :: (Num a) => a -> a
übersetzt:Dies ist als existenzielle Quantifizierung bekannt, was bedeutet, dass es einige Instanzen gibt,
a
für die eine Funktion, wenn sie vom Typ gespeist wird, etwas voma
gleichen Typ zurückgibt, und diese Instanzen gehören alle zur Menge der Zahlen.Daher können wir sehen, dass das Hinzufügen einer Einschränkung (die
a
zur Menge der Zahlen gehören sollte) die Begriffsebene für mehrere mögliche Implementierungen freigibt.Kommen wir nun zu der zweiten Aussage und der, die tatsächlich die Erklärung von
forall
:Eine Freiheit auf Typebene wird zu einer Einschränkung auf Termebene
Lassen Sie uns nun die Funktion auf Typebene freigeben:
Dies bedeutet nun:
Dies bedeutet, dass die Implementierung dieser Typensignatur so erfolgen sollte, dass sie
a -> a
für alle Umstände geeignet ist.Dies schränkt uns nun auf der Begriffsebene ein. Wir können nicht mehr schreiben
weil diese Implementierung nicht befriedigen würde, wenn wir
a
als setzenBool
.a
kann einChar
oder ein[Char]
oder ein benutzerdefinierter Datentyp sein. Unter allen Umständen sollte etwas Ähnliches zurückgegeben werden. Diese Freiheit auf Typebene ist die sogenannte universelle Quantifizierung und die einzige Funktion, die dies erfüllen kann, istdas ist allgemein als die
identity
Funktion bekanntDaher
forall
handelt es sich um eineliberty
auf Typebene, deren eigentlicher Zweck darin besteht,constrain
die Begriffsebene einer bestimmten Implementierung zuzuordnen.quelle
Der Grund, warum dieses Schlüsselwort unterschiedlich verwendet wird, besteht darin, dass es tatsächlich in mindestens zwei verschiedenen Typsystemerweiterungen verwendet wird: höherrangige Typen und Existentials.
Es ist wahrscheinlich am besten, diese beiden Dinge getrennt zu lesen und zu verstehen, anstatt zu versuchen, eine Erklärung dafür zu erhalten, warum 'forall' in beiden gleichzeitig eine angemessene Syntax ist.
quelle
Wie ist existenziell existenziell?
Eine Erklärung, warum
forall
indata
Definitionen isomorph zu(exists a. a)
(Pseudo-Haskell) ist, findet sich in Wikibooks "Haskell / Existential quantified types". .Das Folgende ist eine kurze wörtliche Zusammenfassung:
MkT x
Welche Art von Pattern Matching / Dekonstruktion gibt esx
?x
kann ein beliebiger Typ sein (wie imforall
) angegeben, und daher ist der Typ:Daher sind die folgenden isomorph:
forall bedeutet forall
Meine einfache Interpretation von all dem ist, dass "
forall
wirklich" für alle "bedeutet". Eine wichtige Unterscheidung zu machen , ist die Wirkung desforall
auf der Definition im Vergleich Funktion Anwendung .A
forall
bedeutet die Definition des Werts oder der Funktion polymorph sein muss.Wenn es sich bei der zu definierenden Sache um einen polymorphen Wert handelt , bedeutet dies, dass der Wert für alle geeigneten Werte gültig sein muss
a
, was sehr restriktiv ist.Wenn das zu definierende Objekt eine polymorphe Funktion ist , bedeutet dies, dass die Funktion für alle geeigneten gültig sein muss
a
, was nicht so einschränkend ist, denn nur weil die Funktion polymorph ist, bedeutet dies nicht, dass der angewendete Parameter polymorph sein muss. Das heißt, wenn die Funktion gültig für alle ista
, dann umgekehrt jede geeignetea
kann angewandt auf die Funktion. Der Typ des Parameters kann jedoch nur einmal in der Funktionsdefinition ausgewählt werden.Wenn ein
forall
in der Funktion Parametertyp ist (dh einRank2Type
) , dann bedeutet es , die angewandten Parameter sein muss wirklich polymorphe, mit der Idee , konsequent seinemforall
Mittel Definition polymorph ist. In diesem Fall kann der Typ des Parameters in der Funktionsdefinition mehrmals ausgewählt werden ( "und wird durch die Implementierung der Funktion ausgewählt", wie von Norman hervorgehoben ).Daher der Grund, warum existenzielle
data
Definitionen erlaubt jedera
ist , weil die Daten Konstruktor eine polymorph Funktion :Art von MkT ::
a -> *
Das heißt
a
, auf die Funktion kann jede angewendet werden. Im Gegensatz zu beispielsweise einem polymorphen Wert :Art von WertT ::
a
Dies bedeutet, dass die Definition von valueT polymorph sein muss. In diesem Fall
valueT
kann als leere Liste[]
aller Typen definiert werden.Unterschiede
Obwohl die Bedeutung für
forall
inExistentialQuantification
und konsistent istRankNType
, haben Existentiale einen Unterschied, da derdata
Konstruktor beim Mustervergleich verwendet werden kann. Wie im ghc-Benutzerhandbuch dokumentiert :quelle