ocaml的树简单的功能

我创建了一个树ocaml的树简单的功能

type 'a tree = { 
     mutable cont: 'a; 
     mutable left: 'a bin_tree; 
     mutable right: 'a bin_tree 
} 
and 'a bin_tree = 
    Empty 
    | Node of 'a tree;;

，我疲于应付一些简单的功能做这样

插入元件（到propper子树，无重复）
使两个二叉树的联合

我googled我的问题，但我不断得到错误。例如：

let rec insert x tree = 
match tree with 
Empty -> Node(x, Empty, Empty) 
| Node(y, left, right) -> 
    if x <= y then Node(y, insert x left, right) 
      else Node(y, left, insert x right)

，或者如果我尝试：

let rec insert x = function 
Empty -> Node(Empty, x, Empty) 
| Node(lb, r, rb) -> if x < r then Node(insert x lb, r, rb) 
else Node{lb; r; insert x rb} ;;

我经常收到语法错误。

来源

2013-05-12 prima

你的匹配模式应该包含{和}匹配记录，以便代码

match tree with 
    Empty -> false 
    | Node { cont=x; left=l; right=r } -> (*something here .... *)

其实，一个language extension for record notation许可证，以避免字段标签时，模式变量具有相同的名称作为字段，所以不是编码模式Node { cont=cont; left=left; right=right }您可以编码Node{cont;left;right}

您也可以查看Ocaml的stdlib/set.ml源文件。请注意，'a bin_tree类型几乎等于'a tree option。

来源

2013-05-12 12:25:04

好的，所以我试着插入： 'let rec插入x tree = 匹配树与空 - > Node {x;空的;空}} |节点{续;剩下; right} - > 如果x <= y，则Node {y;向左插入x; right} else Node {y;剩下;插入x右} ;;' 我不认为这是正确的，虽然 – prima 2013-05-12 13:41:37

至少它可能编译。我无法分辨这是否是您的老师所期望的。他可能希望你保持树木的平衡... – 2013-05-12 13:43:34

树木应该平衡适当，是的。左侧子树包含比节点更小的元素，右侧则包含更大的元素。并且不应该有重复。 – prima 2013-05-12 13:47:04

为什么你为你的树使用可变记录？ OCaml程序员更喜欢使用不可变数据结构。在这里，树的可变性不会提高复杂性，但会引入错误。

这是如何实现的树木在持久性方式：

type 'a tree = 
| Empty 
| Node of 'a * 'a tree * 'a tree

，它实际上是这种类型的，你在代码中使用了member和insert。

来源

2013-05-12 13:06:08 Thomash

我正准备参加考试，这是我们作为考试准备的问题之一。我不知道他们为什么选择制作可变数据。 – prima 2013-05-12 13:39:53

我不得不说它看起来不像我惯用的OCaml代码。这种类型看起来太复杂了，可变性是可疑的。 – 2013-05-12 15:13:58

ocaml的树简单的功能

回答

相关问题