OCaml，与refs和树的意外行为

我试图给一棵树的每个元素分配一个数字。我认为使用refs会使任务更容易，但是我遇到了一个奇怪的行为：分配的数字不是唯一的，并且没有出现清晰的模式。我设法修复了这个bug（添加了let unboxed = !second_ref in行），但我不明白发生了什么。OCaml，与refs和树的意外行为

输出控制台中的第一棵树只是确保print_tree函数输出它应该。

但是，第二个打印的预期输出应该与第三个树完全相同。我错过了什么？

type ('a, 'b) tree = 
    | Node of 'a * ('a, 'b) tree * ('a, 'b) tree 
    | Leaf of 'b 

let print_tree tree string_of_node string_of_leaf = 
    let rec print indent tree = 
    match tree with 
    | Leaf (l) -> print_string (indent^" -> "^string_of_leaf(l)^"\n") 
    | Node (n, left, right) -> 
     Printf.printf "%s-----------\n" indent; 
     print (indent^"|   ") left; 
     Printf.printf "%s%s\n" indent (string_of_node(n)); 
     print (indent^"|   ") right; 
     Printf.printf "%s-----------\n" indent 
    in print "" tree 

let myTree = Node(1,Node(2,Leaf(3),Leaf(4)),Node(5,Leaf(6),Leaf(7))) ;; 

let first_ref = ref 0 ;; 
let rec bug tree = 
    first_ref := !first_ref+ 1; 
    match tree with 
    |Leaf(a) -> Leaf(!first_ref) 
    |Node(n,l,r) -> Node(!first_ref, bug l, bug r) ;; 

let second_ref = ref 0 ;; 
let rec bug_fixed tree = 
    second_ref := !second_ref + 1; 
    let unboxed = !second_ref in 
    match tree with 
    |Leaf(a) -> Leaf(unboxed) 
    |Node(n,l,r) -> Node(unboxed, bug_fixed l, bug_fixed r) ;; 


let bug_tree = bug myTree ;; 
let bug_fixed_tree = bug_fixed myTree ;; 

print_tree myTree string_of_int string_of_int ; 
print_tree bug_tree string_of_int string_of_int ; 
print_tree bug_fixed_tree string_of_int string_of_int ;

输出如下：

----------- 
|   ----------- 
|   |   -> 3 
|   2 
|   |   -> 4 
|   ----------- 
1 
|   ----------- 
|   |   -> 6 
|   5 
|   |   -> 7 
|   ----------- 
----------- 
----------- 
|   ----------- 
|   |   -> 7 
|   7 
|   |   -> 6 
|   ----------- 
7 
|   ----------- 
|   |   -> 4 
|   4 
|   |   -> 3 
|   ----------- 
----------- 
----------- 
|   ----------- 
|   |   -> 7 
|   5 
|   |   -> 6 
|   ----------- 
1 
|   ----------- 
|   |   -> 4 
|   2 
|   |   -> 3 
|   ----------- 
-----------

来源

2017-08-01 RUser4512

这可能是题外话这里，但你tree'让我为难的类型'的定义。叶子可能与节点有不同的类型？ – RichouHunter

在你bug功能，有此问题的表达：

Node(!first_ref, bug l, bug r)

其行为依赖的参数评估的顺序：bug l和bug r增加first_ref，所以传递的值可能不是你想要的。

您可以通过执行例如强制命令：

let v = !first ref in 
let new_l = bug l in 
let new_r = bug r in 
Node (v, new_l, new_r)

来源

2017-08-01 13:00:25

只需为此答案添加一点上下文。从理论上讲，由于没有副作用，评估顺序在纯粹的功能语言中并不重要。当然，使用引用打破了这种情况，因此是局部绑定技巧。值得注意的是，在OCaml中没有规定评估顺序，这与语言的功能性相一致。 – RichouHunter

@RichouHunter，OCaml远不是纯粹的，除了可变状态之外还有很多其他的效果，例如，例外，非终止，I/O等等。恕我直言，没有指定评估顺序的借口。这是它最令人讨厌的陷阱之一。 –

我完全同意@AndreasRossberg。不过，我想知道现在指定它的影响是否会影响现有的实现和代码库。 – RichouHunter

OCaml，与refs和树的意外行为

回答

相关问题