OCaml, comportement inattendu avec les références et les arbres

Question

J'essayais d'attribuer un nombre à chaque élément d'un arbre. Je pensais que l'utilisation de refs rendrait la tâche plus facile, mais j'ai rencontré un comportement étrange: les numéros attribués n'étaient pas uniques et aucun motif clair n'est apparu. J'ai réussi à corriger le bug (en ajoutant la ligne let unboxed = !second_ref in) mais je ne comprends pas ce qui s'est passé.

La première arborescence de la console de sortie s'assure que la fonction print_tree génère ce qu'elle doit. Cependant, la sortie attendue pour la deuxième impression doit être exactement la même que la troisième arborescence. Qu'est-ce que je rate ?

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 ; 

La sortie est la suivante:

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

Answer 1

Dans votre fonction bug, il y a cette expression problématique:

Node(!first_ref, bug l, bug r) 

Son comportement dépend de l'ordre d'évaluation des arguments: bug l et bug r incrémenter first_ref, donc la valeur qui est passée peut ne pas être ce que vous voulez.

Vous pouvez forcer l'ordre en faisant par exemple:

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