Anonyme rekursive Funktionen in OCaml

Question

Wie machen Sie eine anonyme rekursive Funktion (etwas einfaches zum Beispiel factorial n?) Ich habe gehört, dass es möglich ist, aber keine Ahnung, wie es in OCaml funktioniert.

let a = 
    fun x -> .... 

Ich weiß nicht, wie es geht zu halten ...

Answer 1

Hier ist eine Definition von factorial nur anonyme Funktionen:

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

Es die Verwendung des -rectypes erfordert Flagge.

Hier ist eine Sitzung zeigt, dass es funktioniert:

$ rlwrap ocaml -rectypes 
     OCaml version 4.03.0 

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1));; 
val fact : int -> int = <fun> 
# fact 8;; 
- : int = 40320 

ich betrogen ein wenig durch die Y Combinator hier aufzublicken: Rosetta Code: Y Combinator

aktualisieren

Haftungsausschluss: Sie täte besser zu lesen auf Lambda-Kalkül, Fixpunkte und den Y-Combinator, als Ihre Informationen von mir zu bekommen. Ich bin kein Theoretiker, nur ein bescheidener Praktizierender.

Nach der eigentlichen Berechnung ist fast unmöglich (aber auf jeden Fall lohnt sich, ich bin mir sicher). Aber auf einem hohen Niveau sind die Ideen so.

Die erste Zeile der Definition ist der Y-Combinator, der im Allgemeinen den Fixpunkt einer Funktion berechnet. Zufällig ist eine rekursive Funktion der Fixpunkt einer Funktion von Funktionen zu Funktionen.

Das erste Ziel ist also, die Funktion zu finden, deren Fixpunkt die faktorielle Funktion ist. Das ist die zweite Zeile der Definition. Wenn Sie eine Funktion vom Typ int -> int eingeben, erhalten Sie eine weitere Funktion vom Typ int -> int zurück. Und wenn Sie ihm die faktorielle Funktion geben, gibt es Ihnen die faktorielle Funktion zurück. Dies bedeutet, dass die faktorielle Funktion ihr Fixpunkt ist.

Wenn Sie also den Y-Combinator auf diese Funktion anwenden, erhalten Sie tatsächlich die faktorielle Funktion.

Answer 2

Lassen Sie mich versuchen, ein wenig auf Jeffrey Scofields Antwort zu erweitern. Eine nicht-anonyme rekursive Definition der Fakultätsfunktion könnte

let rec fact n = 
    if n < 2 then 1 else n * fact (n - 1) 

Das erste Problem auftreten, wenn Sie versuchen, eine anonyme rekursive Funktion ist zu definieren, wie der tatsächlichen rekursiven Aufruf (fact (n - 1) in unserem Fall) zu tun. Für einen Anruf brauchen wir einen Namen und wir haben keinen Namen für eine anonyme Funktion. Die Lösung besteht darin, einen temporären Namen zu verwenden. Mit dem temporären Namen f ist die Definition Körper nur

fun n -> if n < 2 then 1 else n * f (n - 1) 

Dieser Begriff keinen Typ hat, weil die „temporären Namen“ f ungebunden ist. Aber wir können es in einen Wert umwandeln, der einen Typ hat, indem wir auch f begrenzen. Lassen Sie uns das Ergebnis g nennen:

let g = fun f n -> if n < 2 then 1 else n * f (n - 1) 

g im Moment noch nicht anonym ist, aber nur, weil ich wieder darauf beziehen möchten. Beachten Sie, dass g den Typ (int -> int) -> (int -> int) hat. Was wir wollen (die faktorielle Funktion) hat den Typ (int -> int). So nimmt g etwas von dem Typ, den wir wollen (in diesem Fall ein Funktionstyp), und erzeugt etwas vom selben Typ. Die Intuition ist, dass g eine Approximation der Fakultät Funktion, nämlich eine Funktion f, die für alle n bis zu einer Grenze N funktioniert und gibt eine bessere Näherung, nämlich eine Funktion, die für alle funktioniert n bis zu N + 1.

Schließlich brauchen wir etwas, das g in eine tatsächliche rekursive Definition verwandelt. Dies ist eine sehr generische Aufgabe. Erinnern Sie sich daran, dass g die Approximationsqualität verbessert. Die endgültige faktorielle Funktion fact ist eine, die nicht weiter verbessert werden kann. Die Anwendung von g auf fact sollte also genauso sein wie nur fact. (Das ist tatsächlich nur vom Standpunkt des Werts wahr. Die tatsächliche Berechnung, die g fact n für einige n inhärent ist, unterscheidet sich von der von nur fact n. Aber die zurückgegebenen Werte sind die gleichen.) Mit anderen Worten, fact ist ein Fixpunkt von g . Was wir brauchen, ist etwas, das Fixpunkte berechnet.

Zum Glück gibt es eine einzige Funktion, die das tut: Der Y-Kombinator. Vom Standpunkt des Wertes ist der Y-Kombinator (lassen Sie uns y in OCaml verwenden, da Großbuchstaben für Konstruktoren reserviert ist) durch die Tatsache definiert, dass y g = g (y g) für alle g: gegeben einige Funktion g, der Kombinator einen seiner Fixpunkte zurückgibt. Folglich ,

y : (`a -> `a) -> `a 

In unserem Fall ist die Variable vom Typ wird durch (int -> int) instanziiert. Eine Möglichkeit y definieren würde

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x)) 

sein, aber dies funktioniert nur mit lazy evaluation (wie, glaube ich, Haskell hat). Da OCaml eifrig bewertet wird, erzeugt es einen Stapelüberlauf, wenn es verwendet wird. Der Grund dafür ist, dass so etwas wie OCaml y g 8 in

g (y g) 8 
g (g (y g)) 8 
g (g (g (y g))) 8 
... 

, ohne jemals zu drehen versucht immer g zu rufen. Die Lösung ist innerhalb von y latenten Berechnung zu verwenden:

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a) 

Ein Nachteil ist, dass y nicht für beliebige Arten funktioniert nicht mehr. Es funktioniert nur für Funktionstypen.

y : ((`b -> `c) -> (`b -> `c)) -> (`b -> `c) 

Sie haben aber trotzdem nach rekursiven Definitionen von Funktionen gefragt, nicht nach rekursiven Definitionen anderer Werte. Also, unsere Definition der Fakultät Funktion ist y g mit y und g wie oben definiert. Weder y noch g sind noch anonym, aber das behoben werden kann leicht sein:

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

UPDATE:

definieren y funktioniert nur mit der -rectypes Option. Der Grund ist, dass wir x auf sich selbst anwenden.