在OCaml中使用数据结构的正确方法

Question

好的,我binary search tree在OCaml 写了一个.

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通往树的正确方法吗？

我的意思是,我想我不应该声明root,每次我再次更改变量root的值,对吧？

如果是这样,我怎么能始终保持根并且可以随时在树中插入值？

Answer 1

这看起来像是插入树中的好功能代码.它在插入过程中不会改变树,而是创建一个包含该值的新树.不可变数据的基本思想是你不"保留"东西.您计算值并将它们传递给新函数.例如,这是一个从列表中创建树的函数:

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.因为名称相同,所以隐藏了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

这是从树中删除值的一些代码.它使用辅助函数来连接两个已知不相交的树(此外,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)

(希望我不只是破坏你的功课!)