Structure de données OCaml impérative avec des pointeurs?

Question

Est-ce possible?

Salut à tous,

dans ma classe on nous a dit de mettre en œuvre arbres binaires de recherche en OCaml, en utilisant la programmation fonctionnelle et impérative. Nous suivons un ADT et implémentation en Pascal, un langage procédural où les pointeurs sont utilisés.

Voici comment la structure de données ressemble à:

# Pascal 
type 
    tKey  = integer; 
    tPos  = ^tNode; 
    tNode  = record 
      key   : tKey; 
      left, right : tPos; 
      end;  
    tBST = tPosT; 

Nous avons également eu quelques opérations BST de base. Voici un exemple d'un, si cela pouvait aider:

# Pascal 
procedure add_key(VAR T : tBST; k:tKey); 
var new, parent, child : tBST; 
begin 
    createNode(new); 
    new^.key := k; 
    new^.left := nil; 
    new^.right := nil; 

    if T=nil then 
     T := new 
    else begin 
     parent := nil; 
     child := T; 
     while (child <> nil) and (child^.key <> k) do begin 
    parent := child; 
    if k < child^.key then 
     child := child^.left 
    else 
     child := child^.right; 
     end; 

     if (child = nil) then 
    if k < parent^.key then 
     parent^.left := new 
    else 
     parent^.right := new; 
     { duplicates are ignored } 
    end; 
end; 

Voici comment mon fonctionnel (si cela a du sens) structure de données ressemble à:

type key = 
    Key of int;; 

type bst = 
    Empty 
    | Node of (key * bst * bst);; 

Cependant, j'ai de gros problèmes en utilisant la facette impérative de OCaml. Je dois le rendre aussi similaire que possible à l'implémentation Pascal et je ne connais pas les possibilités de structures de données et de pointeurs dans OCaml puisque j'ai toujours programmé en utilisant récursif et ainsi de suite. Je pensais utiliser plusieurs "let", if et else, mais je ne sais pas comment définir ma structure de données. Apprécierait énormément de contribution à ce sujet.

Answer 1

D'après ce que je comprends que vous auriez un type comme celui-ci:

type key = int 

type t = Empty | Node of t * key * t 

Mais votre fonction d'ajout ne devrait pas ressembler à ceci:

let rec add x t = 
    match t with 
    | Empty -> 
     Node (Empty, x, Empty) 
    | Node (l, v, r) -> 
     let c = compare x v in 
     if c = 0 then t 
     else if c < 0 then Node (add x l, v, r) 
     else Node (l, v, add x r) 

Parce que ce ne fonctionne que.

Peut-être que vous pourriez changer votre type de:

type t = Empty | Node of t ref * key * t ref 

Et essayer d'adapter la fonction add à ce type.