在OCaml中使用数据结构的正确方法 [英] The right way to use a data structure in OCaml

问题描述

好吧，我在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屋！