Doing nothing on a pattern matching in OCaml

Question

When I am programming functions on trees in OCaml I always face this recurrent problem : when I get to the leaves of the tree I would like to return nothing but still want my programm to continue.

To be more clear sometimes I have exercises that asked to find a particular node n so I can do the following : (for simplicity I am doing this on binary trees here) :

let rec find_node n tree = match tree with 
|Nil   ->  (* I don't want my program to stop here but then what can I return ?*) 
|Node(l, k, r) as t when k =n -> t
|Node(l, _, r) -> find_node n l; find_node n r

I am using the following representation of binary trees :

type b_tree = Nil | Node of b_tree * int * b_tree 

So basically I would like my programm to continue running until it finds what it wants, yet since a function in OCaml has only one return type I can't do somehting like :

let rec find_node n tree = match tree with 
|Nil   ->  ()  (*returning unit type here*)
|Node(l, k, r) as t when k =n -> t
|Node(l, _, r) -> find_node n l; find_node n r

So how can I tell "do nothing" on a pattern case ?

Thank you !

Answer 1

There are two ways to look at this:

1) When you hit Nil in find_node that means that no node was found. You have to return some form of nothing.

1a) You return None, which also means you have to return Some x in the other cases. This is the API flavor with options.

1b) You raise Not_found. This the the API flavor with exceptions.

Some modules follow 1a, other 1b. Some have submodules for the flavors or 2 functions e.g. find_node (exception) and find_node_opt (option). What flavor should you have? That's 50% personal preference and 50% use case. Both are equally valid and both have advantages on the other depending on the use case.

2) Your data type is to blame

I've seen trees defined as

type b_tree = Leaf of int | Node of b_tree * int * b_tree 

That way you don't have a Nil case. On the other hand there is no representation of an empty tree then.

Answer 2

It's possible to return nothing in a pattern matching in ocaml, and here is how you can do it:

[] -> () 

thus, for you exemple, it can be done that way:

let rec find_node n tree = match tree with 
|Nil   -> ()
|Node(l, k, r) as t when k =n -> t
|Node(l, _, r) -> find_node n l; find_node n r

feel free to look at some exemple on this repo:game in ocaml