2

binary search treeOK、 OCaml でa を書きました。

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


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

上記のコードは問題ないと思います。

使うときは書きます

let root = insert 4 Leaf

let root = insert 5 root

...

use/insertこれは木への正しい道ですか？

つまり、ルートを宣言するべきではないと思いますし、変数ルートの値を再度変更するたびに、そうですか?

もしそうなら、ルートを常に保持し、いつでもツリーに値を挿入するにはどうすればよいですか?

4

1 に答える 1

8

これは、ツリーに挿入するための適切な機能コードのように見えます。挿入中にツリーを変更するのではなく、値を含む新しいツリーを作成します。不変データの基本的な考え方は、「保持」しないということです。値を計算し、それらを新しい関数に渡します。たとえば、リストからツリーを作成する関数は次のとおりです。

let tree_of_list l = List.fold_right insert l Leaf

への新しい呼び出しごとに現在のツリーを渡すことで機能しinsertます。

FP の利点の多くは、不変データの使用に由来するため、このように考えることを学ぶ価値があります。ただし、OCaml は混合パラダイム言語です。必要に応じて、参照 (または変更可能なレコード フィールド) を使用して、通常の命令型プログラミングと同様に、値が変化するときにツリーを「保持」できます。

編集：

次のセッションは、変数 x の変更を示していると思うかもしれません。

# let x = 2;;
val x : int = 2
# let x = 3;;
val x : int = 3
#

ただし、これを見る方法は、これらはたまたま両方に x という名前の 2 つの異なる値であるということです。名前が同じなので、x の古い値は隠されています。しかし、古い値にアクセスする別の方法があれば、まだそこにあるでしょう。おそらく、以下は物事がどのように機能するかを示しています。

# let x = 2;;
val x : int = 2
# let f () = x + 5;;
val f : unit -> int = <fun>
# f ();;
- : int = 7
# let x = 8;;
val x : int = 8
# f ();;
- : int = 7
#

x値 8で名前が付けられた新しいモノを作成しても、何に影響はありませんf。x定義されたときに存在していたものと同じ古いものをまだ使用しています。

編集2：

ツリーから値を不変に削除することは、値を追加することに似ています。つまり、既存のツリーを実際に変更するわけではありません。不要な値のない新しいツリーを作成します。挿入してもツリー全体がコピーされないのと同じように (前のツリーの大部分が再利用されます)、削除してもツリー全体がコピーされません。変更されていないツリーの部分は、新しいツリーで再利用できます。

編集 3

ツリーから値を削除するコードを次に示します。これは、互いに素であることが知られている 2 つのツリーに隣接するヘルパー関数を使用します (さらに、a のすべての値が b のすべての値よりも小さい)。

let rec adjoin a b =
    match a, b with
    | Leaf, _ -> b
    | _, Leaf -> a
    | Node (v, al, ar), _ -> Node (v, al, adjoin ar b)

let rec delete x = function
    | Leaf -> Leaf
    | Node (v, l, r) ->
        if x = v then adjoin l r
        else if x < v then Node (v, delete x l, r)
        else Node (v, l, delete x r)

（私があなたの宿題を台無しにしていないことを願っています！）

于 2013-01-21T14:44:07.043 に答える