How do I check if there is a child at an n position in a n-ary tree in OCaml?

Question

I'm trying to make a function that, given a tuple list (I don't know if tuple is the correct term, what i mean is a (x,y) list) and an n-ary tree, it returns the leaf that you get from checking if a key in the tuple is present in the tree, and taking the child in the position of the value associated to that key, if it doesn't exist, raise an error.

I know I didn't explain it well, so I'll help myself with an example. tuple list = [(1,3);(2,2);(3,1);(10,1)] if the the root's value is 1 then it will check the third child (if not it will go on with the list), then if the child's value is 10, it will check his first child until it will find a leaf.

What i thought to do was to first use List.map to remove the elements that don't match with a tuple's key and the childs that are not in the associated value's value position, and then do the same to their childs recursively.

Here is what I did:

type 'a ntree = Tr of 'a * 'a ntree list;;
let leaf x = Tr(x,[]);; 

let alb = Tr(1,[Tr(2,[leaf 3; leaf 4; leaf 2]);Tr(5,[leaf 11; leaf 10]);Tr(3,[leaf 9; leaf 7; leaf 10])]);;
let guida = [(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)];;


let rec cerca_foglia guida (Tr(x,tlist)) =
  match tlist with
    [] -> x
  |_ -> List.map(fun a -> List.mem_assoc x guida && (*a.position = List.nth tlist List.assoc x guida*)) (cerca tlist)
and cerca = function
    [] -> raise NotFound
  |[t] -> cerca_foglia guida t
  |t::rest -> 
      try cerca_foglia guida t
      with NotFound -> cerca rest
          

Of course, a.position does not exist, so how can I check it?

I also tried it differently:

let rec cerca_foglia guida (Tr(x,tlist)) =
  match tlist with
    [] -> x
  |_ -> List.map(fun a -> a = List.nth tlist List.assoc x guida) (cerca tlist)
and cerca = function
    [] -> raise NotFound
  |[t] -> if List.mem_assoc t guida then  cerca_foglia guida t else raise NotFound
  |t::rest -> 
      try cerca_foglia guida t
      with NotFound -> cerca rest

But it still gives errors...How can I solve it?

Answer 1

After much pondering, I think I might have understood some of this. I have written two functions: find_child and find_child2.

type 'a ntree = Tr of 'a * 'a ntree list

let leaf x = Tr(x,[])

let alb = Tr(1,[Tr(2,[leaf 3; leaf 4; leaf 2]);Tr(5,[leaf 11; leaf 10]);Tr(3,[leaf 9; leaf 7; leaf 10])])

let guida = [(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)]

let rec find_child (Tr (root, children) as tree) =
  function
  | [] -> None
  | (k, v)::_ when root = k -> Some (List.nth children (v - 1))
  | _::kvs -> find_child tree kvs

let rec find_child2 (Tr (root, children) as tree) key_val_list =
  match children with
  | [] -> Some tree
  | _ ->
    (match key_val_list with
     | [] -> None
     | (k, v)::kvs when root = k -> find_child2 (List.nth children (v - 1)) kvs
     | _::kvs -> find_child2 tree kvs)

The find_child function stops at the first match it finds. So evaluating find_child alb guida yields:

utop # find_child alb guida;;
- : int ntree option = Some (Tr (3, [Tr (9, []); Tr (7, []); Tr (10, [])]))

The find_child2 function does something similar, but it only stops if it finds a "leaf" or if it doesn't find any of the keys it's looking for in the current node.

utop # find_child2 alb guida;;
- : int ntree option = Some (Tr (9, []))

And refactoring find_child2 a bit to clean it up and handle the Failure "nth" exception that may occur:

let rec find_child3 (Tr (root, children) as tree) key_val_list =
  match children, key_val_list with
  | [], _ -> Some tree
  | _, [] -> None
  | _, (k, v)::kvs when root = k -> 
    (match List.nth children (v - 1) with
     | child -> find_child3 child kvs
     | exception (Failure "nth") -> None)
  | _, _::kvs -> find_child3 tree kvs
  | exception Failure "nth" -> None

Sketching out what the recursion looks like when we evaluate find_child3 alb guida:

find_child3 alb guida

find_child3 (Tr(1,
               [Tr(2,[leaf 3; leaf 4; leaf 2]);
                Tr(5,[leaf 11; leaf 10]);
                Tr(3,[leaf 9; leaf 7; leaf 10])])) 
            [(1,3);(2,2);(3,1);(10,1);(16,2);(11,2)]

find_child3 (Tr(3,[leaf 9; leaf 7; leaf 10])) 
            [(2,2);(3,1);(10,1);(16,2);(11,2)]

find_child3 (Tr(3,[leaf 9; leaf 7; leaf 10])) 
            [(3,1);(10,1);(16,2);(11,2)]

find_child3 (leaf 9) [(10,1);(16,2);(11,2)]

Some (Tr (9, []))

Is this the kind of thing you're looking for?