CODEWITHSUNDEEP
ocaml
BMBM
BMBM

Reputation: 16013

Why is my entry in the HashTable not found?

I have the following code:

let to_permutation pairs max_el =
  let tbl = Hashtbl.create 100 in
  let rec aux i collector = 
    if i > max_el then collector
    else 
      match Hashtbl.find_opt tbl i with
        None ->   
          ignore (Printf.printf "NOT found \n");
          Hashtbl.add tbl i 1;
          aux (i + 1) (List.append (List.hd collector) [List.assoc i pairs] :: List.tl collector)           
      | Some _ ->
          ignore (Printf.printf "Found\n");
          aux (i + 1) (List.append [[]] collector)  
  in
  aux 1 [[]];;

What it's supposed to do: when I give the function a list of pairs, then I want it to generate me cycles of mapped integers ( based on the pairs. )

Example: to_permutation [(1, 6); (2, 3); (3, 5); (4, 1); (5, 2); (6, 4)] 6;; should return something like [[1; 6; 4]; [2; 3; 5]];.

However I'm not even close to this, because the lookup to check if I already visited an element (and thus detected a cycle) fails. The output of the program:

to_permutation [(1, 6); (2, 3); (3, 5); (4, 1); (5, 2); (6, 4)] 6;;
NOT found 
NOT found 
NOT found 
NOT found 
NOT found 
NOT found 
- : int list list = [[6; 3; 5; 1; 2; 4]]

Although I insert into the hash table, it never finds an element. What am I doing wrong?

Upvotes: 0

Views: 123

Answers (1)

octachron
octachron

Reputation: 18892

Through the call to aux i, you are maintaining the invariant that the table tbl only contains keys that are strictly inferior to i. Thus find_opt tbl i always return None, and you add an i key to tbl before calling aux (i+1) preserving the invariant stated earlier.

Upvotes: 1

Related Questions