ML-Funktion vom Typ 'a ->' b

19

Unser Professor hat uns gebeten, uns eine Funktion in OCaml zu überlegen, die den Typ hat

'a -> 'b

dh eine Funktion eines Arguments, das alles sein kann und das etwas anderes zurückgeben kann.

Ich dachte an die Verwendung raisein einer Funktion, die ihr Argument ignoriert:

let f x = raise Exit

Der Professor sagte jedoch, es gebe eine Lösung, die keine Funktion in der Standardbibliothek benötige. Ich bin verwirrt: Wie kannst du eine machen, 'bwenn du überhaupt keine hast?

Ich frage hier und nicht bei Stack Overflow, weil ich verstehen will, was los ist. Ich möchte nicht nur ein Programm ohne Erklärung sehen.

Gilles 'SO - hör auf böse zu sein'
quelle
2
Bitte zielen Sie in Ihrer Antwort auf die Lernprogrammierung für CS101-Schüler ab, nicht auf den Typentheoretiker, zu dem Ihre Antwort ihn später inspirieren könnte.
Gilles 'SO- hör auf böse zu sein'
Es wäre hilfreich, wenn Sie erklären würden, wie Sie herausfinden raisewürden , dass dies funktionieren würde. Wir wissen also, wie Sie am besten erklären können, warum die Lösung, nach der Ihr Professor sucht (die aus den gleichen Gründen raisefunktioniert , die auch funktioniert), funktioniert.
13.
@ sepp2k raise : exn -> 'aDamit ich den Rückgabewert erhalten kann, ignoriere ich einfach das Argument.
Gilles 'SO - hör auf böse zu sein'
1
Folgefrage: ML funktioniert von polymorphen Listen zu polymorphen Listen
Gilles 'SO - hör auf, böse zu sein'
2
Siehe auch Warum liefert der Hindley-Milner-Algorithmus niemals einen Typ wie t1 -> t2? Diskussion einer theoretischeren Einstellung.
Gilles 'SO- hör auf, böse zu sein'

Antworten:

18

Das Skelett ist let f x = BODY. In BODY müssen Sie x verwenden nur in generischer Weise (zum Beispiel tut es nicht , dass erwartet ganze Zahlen auf eine Funktion senden), und Sie müssen einen Wert zurückgeben jeden anderen Typ. Aber wie kann der letzte Teil wahr sein? Die einzige Möglichkeit, die Anweisung "Für alle Typen 'bist der zurückgegebene Wert ein Wert vom Typ 'b" zu erfüllen , besteht darin, sicherzustellen, dass die Funktion nicht zurückgegeben wird. Es gibt genau zwei Möglichkeiten: entweder BODY-Fehler oder es wird nicht beendet. Die Funktionsstörungen raise, die folgenden werden nicht beendet:

let rec f x = f x
rgrig
quelle
19

Zunächst einige Bemerkungen. Es ist nicht möglich, nur die typisierte Kern-Lambda-Rechnung zu verwenden, 'a -> 'bda das Typisierungssystem (über den Curry Howard-Isomorphismus ) mit der intuitionistischen Logik korrespondiert und die entsprechende Formel A → Bkeine Tautologie ist.

Andere Erweiterungen wie Tupel und Übereinstimmungen / Bedingungen bewahren immer noch eine gewisse logische Konsistenz, indem sie Produkttypen hinzufügen, *die dem logischen Zusammenhang entsprechen, und und Summentypen, |die dem oder entsprechen . Erwarten Sie auch hier nicht, dass sie diesen 'a -> 'bTyp produzieren, da man damit eine Formel nachweisen kann, die keine Tautologie ist.

Sie haben also nur die Chance, andere Konstruktionen zu verwenden, die sich der Logik entziehen, wie raise(aber das dürfen Sie in diesem Fall nicht)… oder let rec! Rekursion ermöglicht die Erstellung von Programmen, die niemals beendet werden, und deren Ergebnisse können mit einem beliebigen Rückgabetyp versehen werden, da sie niemals erzeugt werden. Wenn Sie sich nun die trivialste nicht terminierende Funktion überlegen (die, die sich selbst direkt aufruft, um ein Ergebnis zurückzugeben):

let rec f x = f x

Sie werden feststellen, dass der Typ genau ist 'a -> 'b: Unabhängig vom angegebenen Argument kann davon ausgegangen werden, dass das Ergebnis (das niemals berechnet wird) einen beliebigen Typ hat.

Das ist natürlich fkeine interessante Funktion, aber genau darum geht es. In OCaml ist jede Funktion, deren Typ nicht wie eine gültige Formel aussieht, eine verdächtige Funktion.

Stéphane Gimenez
quelle
Der Fragesteller hat ein Wort Ihrer ersten beiden Absätze nicht verstanden, aber ich mag Ihren Satz "Ihre Ergebnisse können mit einem beliebigen Rückgabetyp versehen werden, da sie niemals produziert werden".
Gilles 'SO - hör auf böse zu sein'
1

Mit einem Compiler-Grundelement können Sie Folgendes schreiben:

external magic: 'a -> 'b = "%identity"

(Und tatsächlich bietet die Compiler-Distribution dies, obwohl sie nicht Teil der Sprache ist). Dies ist eine unsichere Identitätsdarstellung.

Ihr Professor möchte das mit ziemlicher Sicherheit nicht. Dies ist jedoch auch die einzige nützliche Funktion mit Typ 'a -> 'b, die mir bekannt ist, und tatsächlich wird sie in der OCaml-Distribution selbst verwendet.

Demi
quelle