OCamlのバイナリ検索ツリー挿入関数

Question

小さい値を挿入したいとします。それは行くだろうNode (insert x left, k, right) 私はinsert x leftを持つことができる方法を理解していない機能の挿入が1つの引数、キーを取ると宣言されている。どのように左にも挿入機能に渡すことができますか？

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

functionキーワードは、一連のパターンとしての機能を定義し、ほとんど常にようなパラメータに名前を与えることなく使用されます。したがって、実際にはinsert関数には2つのパラメータがあります。 functionなし

この定義は同等です：

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

それは一見そう見えるかもしれないが、機能insertは一つではなく二つの引数を持っている - 一つは、あなたが言ったように挿入されるキー、および第二です1つは、キーを挿入するbst_tです。

OCamlでは、それが適用可能な場合はPoint-free programmingのコンセプトが強く推奨されています。それはまさにあなたの挿入機能で起こることです。あなたの関数のバージョンは（通常、冗長な構文で記述された）次の関数のためだけの短手表記です：

BSTは挿入がその関数ツリー、つまり、実行されている木である

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) 

パターンはLeaf | Nodeと一致します。

Answer 3

Ocam1はREPL、すなわち実験に有用な対話的環境を有し、は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> 

read-eval-print-loopには、評価式の値だけでなくそのタイプも表示されます。ここでは、シンボルinsertは "some type 'a"の値をとり、 "そのタイプのバイナリツリー'a"の値をとり、同じバイナリの値を返す関数にバインドされていることがわかります'aタイプの木。

システムについて多くのことを教えてくれるたびに、REPLを使用することを強く推奨します。