Werden Typen in Haskell gelöscht?

13

Haskell hat eine Vorstellung von "generischen Funktionen", die eine gewisse Ähnlichkeit mit gewöhnlichem Lispeln aufweist - da ich weder Erfahrung mit Haskell noch mit gewöhnlichem Lispeln habe, könnte ich hier sehr ungefähr sein. Dies bedeutet, dass man eine generische to_stringEinrichtung definieren kann, um eine Zeichenfolgendarstellung für alle Typen zu definieren. Natürlich muss die Einrichtung in den Sonderfällen definiert werden, aber es gibt eine to_stringFunktion, deren Signatur ist α → string.

Werden Typen in Haskell wie in OCaml gelöscht? Wenn ja, wie unterscheidet sich die Implementierung von "generischen Funktionen" in Haskell von der von "Common Lisp", bei denen Typen dynamisch sind und daher nicht gelöscht werden?

Ich verstehe, dass Implementierungsdetails compilerspezifisch sind, aber es gibt wahrscheinlich Bestimmungen, die vielen oder allen Implementierungen gemeinsam sind.

user40989
quelle
5
Denken Sie daran, dass Sie wahrscheinlich keine nicht triviale Funktion vom Typ definieren können a -> String. Es ist wahrscheinlicher, dass Sie eine Typeinschränkung haben, z Show a => a -> String.
DJG

Antworten:

16

Die Antwort ist bisher irreführend.

Es muss zwischen "parametrischem" und "Ad-hoc-Überladungs" -Polymorphismus unterschieden werden. Parametrisch bedeutet "verhält sich für alle Typen gleich", während "ad-hoc" - was Simon als polymorph bezeichnet - die Implementierung je nach Typ ändert.

Beispiele für beides sind reverse :: [a] -> [a]parametrisch und show :: Show a => a -> String"ad-hoc" überlastet.

Wenn Sie mehr von einer abstrakten Intuition wollen, denke ich, dass es hilfreich ist, die Klassen der natürlichen Sprachverben zu betrachten, die für alle Objekte "funktionieren", wie "besitzen" oder "denken", die keine Einschränkungen für das Objekt darstellen, sondern " zu öffnen "erfordert, dass das, wovon wir sprechen, geöffnet werden kann. Ich kann 'an eine Tür denken' und 'eine Tür öffnen', während es keinen Sinn macht, zB 'einen Baum zu öffnen'. Das Beispiel noch weiter zu führen "öffnen" ist "ad-hoc polymorph" als "ein Fenster öffnen" und "ein Reklamationsticket mit Kundenservice öffnen" sind zwei sehr unterschiedliche Dinge. Wenn das gezwungen zu sein scheint - vergiss es! Für mich geht das.

Beide werden jedoch zur Kompilierungszeit aufgelöst und tatsächlich "gelöscht". Modulo verschiedene GHC-Erweiterungen und Template Haskell, etc. Typen werden in der Tat zur Kompilierungszeit gelöscht und nie zur Laufzeit überprüft.

Parametrisch polymorphe Funktionen verhalten sich für alle Typen gleich, so dass nur ein Codeteil generiert werden muss, während der Compiler beim Kompilieren entscheidet, welche Version einer "typisierten" Funktion an einem bestimmten Programmpunkt ausgeführt werden muss. Aus diesem Grund gibt es auch die Einschränkung einer Instanz pro Typ pro Typklasse und die entsprechende "newtype" -Umgehung.

Die Implementierung ist in SPJs Lehrbuch und Wadler and Blotts Paper zu Typklassen beschrieben .

Kris
quelle
Denkst du, ich sollte meine Antwort löschen?
Simon Bergot
Nein, es ist in Ordnung, wenn Sie davor gewarnt werden, das genaue Vokabular nicht zu treffen
Kris
Könnten Sie etwas näher darauf eingehen, warum es für GHC möglich ist, Typen zu löschen? Liegt es an der Haupttypisierung?
Simon Bergot
2
Im Allgemeinen können zur Laufzeit entweder die parametrisch polymorphen Funktionen nur einmal vorhanden sein und die Ad-hoc-polymorphen Funktionen über eine virtuelle Versandmethode aufrufen, oder der gesamte Code kann für jeden Typ separat generiert und die Aufrufe statisch verknüpft werden. Beide Implementierungen sind aus sprachlicher Sicht korrekt (beachten Sie, dass Haskell keine polymorphen Typen hat; solche können nur mit der GHC- forallErweiterung erstellt werden).
Jan Hudec
Gibt es eine GHC-Erweiterung, mit der Typen nicht gelöscht werden können? Überladung ist statisch und ohne voll abhängige Typen fällt mir nichts ein
Daniel Gratzer
1

Warnung: Mein Hintergrund in CS ist nicht sehr ausgeprägt, daher verwende ich möglicherweise nicht immer das richtige Vokabular und irre mich in einigen Punkten. Sowieso ist hier mein Verständnis:

Ich denke, Sie verwechseln Generika mit Polymorphismus.

Generische Typen wie List<Foo>werden verwendet, um Typen zu beschreiben, die andere Typen als Parameter verwenden, und ermöglichen eine umfassendere Typprüfung.

Eine generische Funktion in haskell könnte sein count:: List a -> Int. Es akzeptiert Listen jeglichen Typs und gibt die Anzahl der Elemente zurück. Es gibt nur eine Implementierung.

Normalerweise können Sie bei der Definition von List nichts über T annehmen. Sie können es nur speichern und zurückgeben.

Ihre to_stringFunktion ist eine polymorphe Funktion, was bedeutet, dass sie sich unter verschiedenen Umständen unterschiedlich verhält. In haskell geschieht dies mit Typenklassen, die wie Adjektive für Typen funktionieren.

Sie haben eine ShowTypenklasse, die eine show :: a -> StringFunktion definiert .

Wenn ein Typ Foodie Typklasse implementiert Show, muss er die Definition von bereitstellen show. Dieser Typ kann dann in Funktionen verwendet werden, die das ShowQualifikationsmerkmal (wie in Show a => a -> whatever) erfordern . Haskell kann keine Typen löschen, da diese Funktionen die korrekte Implementierung der showFunktion finden müssen.

Simon Bergot
quelle
Polymorphe Funktionen werden im allgemeinen lisp als "generische Funktionen" bezeichnet, und ich habe dasselbe (verwirrende) Vokabular verwendet. Ihre Antwort ist nützlich und Ihr letztes Argument ziemlich überzeugend. .-)
user40989
„Es gibt nur eine Implementierung“ - natürlich nur eine, die Sinn macht, aber es sind unendlich viele möglich. Eine Funktion vom Typ a → b hat | b | ^ | a | Mögliche Implementierungen (Anzahl der Funktionen vom Typ Bool → Bool berücksichtigen) und Listen haben keine obere Größenbeschränkung.
Jon Purdy