在OCaml中使用数据结构的正确方法 [英] The right way to use a data structure in OCaml
问题描述
二元搜索树
。 键入'a bstree =
|'a *'的节点a bstree *'a bstree
| Leaf
let rec x = function
|叶 - > Node(x,Leaf,Leaf)
|节点(y,左,右)作为节点 - >
如果x < y然后
Node(y,insert x left,right)
else if x> y然后
Node(y,left,insert x right)
else
node
我猜上面的代码没有问题。
使用它时,我写
let root = insert 4 Leaf
let root = insert 5 root
...
这是正确的方式来使用/插入
到树?
我的意思是,我猜测我不应该声明根,每次我再次更改变量根的值,对吗?
如果是这样,我该如何始终保持根,并可以插入值在任何时候在树中?
这看起来像插入到树中的很好的功能代码。它在插入过程中不突变树,而是创建一个包含该值的新树。不可变数据的基本思想是你不保持事物。您计算值并将其传递给新功能。例如,这是一个从列表中创建树的函数:
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
#
创建一个名为<$值为8的c $ c> x 不会影响 f
。它仍然使用与定义时相同的旧的 x
。
编辑2: strong>
从树中删除一个值不可思议的类似于添加一个值。即,实际上并没有修改现有的树。你创建一个没有你不想要的值的新树。正如插入不复制整个树(它重新使用之前的树的大部分),所以删除也不会复制整个树。没有更改的树的任何部分都可以在新树中重新使用。
编辑3
这是一些从树中删除值的代码。它使用一个辅助函数,它邻接已知不相交的两个树(此外,a中的所有值都小于b中的所有值):
let rec adjacentin ab =
match a,b with
|叶,_ - > b
| _,叶 - > a
| Node(v,al,ar),_ - >节点(v,al,毗邻ar b)
允许rec delete x = function
|叶 - > Leaf
|节点(v,l,r) - >
如果x = v则毗邻l r
如果x < v then Node(v,delete xl,r)
else Node(v,l,delete xr)
(希望我不只是破坏你的功课!)
Ok, I have written a binary search tree
in 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
I guess the above code does not have problems.
When using it, I write
let root = insert 4 Leaf
let root = insert 5 root
...
Is this the correct way to use/insert
to the tree?
I mean, I guess I shouldn't declare the root and every time I again change the variable root's value, right?
If so, how can I always keep a root and can insert a value into the tree at any time?
This looks like good functional code for inserting into a tree. It doesn't mutate the tree during insertion, but instead it creates a new tree containing the value. The basic idea of immutable data is that you don't "keep" things. You calculate values and pass them along to new functions. For example, here's a function that creates a tree from a list:
let tree_of_list l = List.fold_right insert l Leaf
It works by passing the current tree along to each new call to insert
.
It's worth learning to think this way, as many of the benefits of FP derive from the use of immutable data. However, OCaml is a mixed-paradigm language. If you want to, you can use a reference (or mutable record field) to "keep" a tree as it changes value, just as in ordinary imperative programming.
Edit:
You might think the following session shows a modification of a variable x:
# let x = 2;;
val x : int = 2
# let x = 3;;
val x : int = 3
#
However, the way to look at this is that these are two different values that happen to both be named x. Because the names are the same, the old value of x is hidden. But if you had another way to access the old value, it would still be there. Maybe the following will show how things work:
# 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
#
Creating a new thing named x
with the value 8 doesn't affect what f
does. It's still using the same old x
that existed when it was defined.
Edit 2:
Removing a value from a tree immutably is analogous to adding a value. I.e., you don't actually modify an existing tree. You create a new tree without the value that you don't want. Just as inserting doesn't copy the whole tree (it re-uses large parts of the previous tree), so deleting won't copy the whole tree either. Any parts of the tree that aren't changed can be re-used in the new tree.
Edit 3
Here's some code to remove a value from a tree. It uses a helper function that adjoins two trees that are known to be disjoint (furthermore all values in a are less than all values in 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)
(Hope I didn't just spoil your homework!)
这篇关于在OCaml中使用数据结构的正确方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!