Finding the recursive OCaml record type

I am trying to recursively search for a field value in a record, which is a recursive record type.

My post type

type node = {node_name:string; node_branch:node list}

      

        
        
        
      

    

First, I tried to simply traverse the tree as a variable of this type:

let tree = {node_name="trunk"; node_branch=[{node_name="branch1L:1"; node_branch=[{node_name="branch2L:1"; node_branch=[]};
                                                                                  {node_name="foo_node"; node_branch=[]};];};
                                            {node_name="branch1L:2"; node_branch=[]}];}
    in
    let target = "foo_node" in
    print_newline();
    search_tree_for_name target tree;

      

        
        
        
      

    

The idea is that it looks something like this:

                    trunk
            __________|_________
           |                    |
       branch1L:1           branch1L:2
    ______|_______
   |              |
branch2:1       foo_node

      

        
        
        
      

    

So I'm looking for a record that has a field value node_name = foo_node

. The way I overcame this, just to prove my logic:

let rec search_tree_for_name target_name in_tree =
  if in_tree.node_name = target_name then
    (* First check the node_name *)
      Format.printf "[%s] Target node_name found\n" in_tree.node_name
  else
    (* Then evaluate the branches *)
    begin
      match in_tree.node_branch with
      | [] ->
         Format.printf "[%s] Branches: 0; End of branch\n" in_tree.node_name
      | head :: tail ->
         Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch);
         search_tree_for_name target_name head;
         List.iter (search_tree_for_name target_name ) tail;
    end

      

        
        
        
      

    

This gives:

[trunk] Branches: 2
[branch1L:1] Branches: 2
[branch2L:1] Branches: 0; End of branch
[foo_node] Target node_name found
[branch1L:2] Branches: 0; End of branch

      

        
        
        
      

    

Now, I really want to just see if an instance exists, where node_name

is what I'm looking for, so I just want to return a boolean.

What I tried was (I created a new function for testing purposes only):

let rec check_tree_for_name target_name in_tree =
  if in_tree.node_name = target_name then
    begin
    (* First check the node_name *)
      Format.printf "[%s] Target node_name found\n" in_tree.node_name;
      true
    end 
  else
    (* Then evaluate the branches *)
    begin
      match in_tree.node_branch with
      | [] ->
         Format.printf "[%s] Branches: 0; End of branch\n" in_tree.node_name;
         false
      | head :: tail ->
         Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch);
         check_tree_for_name target_name head;
         List.iter (check_tree_for_name target_name ) tail;
    end

      

        
        
        
      

    

I am getting the following error in my function, I am navigating to List.iter

:

Error: This expression has type node -> bool
       but an expression was expected of type node -> unit
       Type bool is not compatible with type unit 

      

        
        
        
      

    

Then I changed the last pattern matching block to

  | head :: tail ->
     Format.printf "[%s] Branches: %i\n" in_tree.node_name (List.length in_tree.node_branch);
     if check_tree_for_name target_name head then true
     else List.iter (check_tree_for_name target_name ) tail;

      

        
        
        
      

    

So, if the if conditions check the return of the function call and the kind of its passing. Now I have one error, but I still have the same error.

I understand that I List.iter

will pass each element of the passed list as the last argument to the function passed to List.iter

. So this should iterate over the elements of my list that I pass to it, and the only outputs are if the field node_name

matches what I'm looking for, or if it is an empty list.

The main difference I see between my two implementations is that the first one continues until all nodes have been evaluated, and the second implementation will continue until I find what I am looking for.

Any suggestions would be appreciated and, if possible, a short explanation of where I am going wrong, or at least highlight where I am going wrong (I feel like I am typing a lot of functional programming concepts, but there are a few more eluding me).