Binary Search Tree einfügen Funktion in OCaml

Question

Angenommen, wir möchten Wert kleiner einfügen. Es wird Node (insert x left, k, right) gehen Ich verstehe nicht, wie wir insert x left haben können, wenn Funktion einfügen als nur ein Argument, der Schlüssel erklärt wird. Wie kann man links auch einfügen Funktion?

type 'a bst_t = 
| Leaf 
| Node of 'a bst_t * 'a * 'a bst_t 

let rec insert x = function 
    | Leaf -> Node (Leaf, x, Leaf) 
    | Node (left, k, right) -> 
    if x < k then Node (insert x left, k, right) 
    else Node (left, k, insert x right) 

Answer 1

Die function Schlüsselwort definiert eine Funktion als eine Reihe von Mustern, und fast immer ohne Angabe des Parameters einen Namen als solche verwendet wird. Die Funktion insert hat also tatsächlich zwei Parameter.

Diese Definition ohne function entspricht:

let rec insert x node = 
    match node with 
    | Leaf -> Node (Leaf, x, Leaf) 
    | Node (left, k, right) -> 
    if x < k then Node (insert x left, k, right) 
    else Node (left, k, insert x right) 

Answer 2

Obwohl es so auf den ersten Blick scheinen mag, Funktion insert hat nicht eine, sondern zwei Argumente - ist der Schlüssel eingesteckt werden, wie Sie gesagt haben, und die zweite Einer ist der bst_t, in den Sie den Schlüssel einfügen möchten.

In OCaml wird das Konzept Point-free programming dringend empfohlen, wenn es angewendet werden kann, und genau das passiert mit Ihrer Insert-Funktion. Ihre Version der Funktion ist nur eine Kurzschreibweise für die folgende Funktion (in normalen geschrieben, die ausführliche Syntax):

let rec insert x bst = match bst with 
| Leaf -> Node (Leaf, x, Leaf) 
| Node (left, k, right) -> 
    if x < k then Node (insert x left, k, right) 
    else Node (left, k, insert x right) 

wo bst den Baum, an dem die Einfügung durchgeführt wird, dh der Baum, der die Funktion passt die Leaf | Node Muster gegen.

Answer 3

Ocaml hat eine REPL, d. H. Eine interaktive Umgebung nützlich zum Experimentieren und mit einer Konversation mit ocaml.

$ ocaml 
     OCaml version 4.02.3 

# type 'a bst_t = 
| Leaf 
| Node of 'a bst_t * 'a * 'a bst_t ;; 
type 'a bst_t = Leaf | Node of 'a bst_t * 'a * 'a bst_t 
# let rec insert x = function 
    | Leaf -> Node (Leaf, x, Leaf) 
    | Node (left, k, right) -> 
    if x < k then Node (insert x left, k, right) 
    else Node (left, k, insert x right)   ;; 
val insert : 'a -> 'a bst_t -> 'a bst_t = <fun> 

Die Lese-eval-print-Schleife zeigt nicht nur den Wert des Ausdrucks ausgewertet, sondern auch seine Art. Hier sehen Sie, dass das Symbol insert an eine Funktion gebunden ist, die den Wert "irgendein Typ 'a" annimmt und eine andere Funktion zurückgibt, die den Wert "einen binären Baum dieses Typs 'a" annimmt und einen Wert derselben Binärzahl zurückgibt Baum von 'a Art.

Ich empfehle dringend, REPLs zu verwenden, wenn Sie sie haben, da sie Ihnen viel über das System erzählen.