CODEWITHSUNDEEP
ocaml
1597846254899
1597846254899

Reputation: 31

Doing nothing on a pattern matching in OCaml

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 !

Upvotes: 1

Views: 4131

Answers (3)

Slim Mesbah
Slim Mesbah

Reputation: 1

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

Upvotes: 0

Goswin von Brederlow
Goswin von Brederlow

Reputation: 12332

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.

Upvotes: 0

Andreas Rossberg
Andreas Rossberg

Reputation: 36098

You need to ask yourself: in the third case, how do you know that the first recursion found a result? How do you distinguish this from an unsuccessful recursion and what do you do in either case? Also, what if there is no node meeting your criterion in the entire tree?

So "doing nothing" is not what you want, you somehow need to indicate that nothing was found.

One obvious way to resolve all this is by returning an option, which would yield the following code:

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

This has return type (b_tree * int * b_tree) option, describing the node attributes, or being None when no node has been found.

Upvotes: 6

Related Questions