Fatal error: exception Match_failure("main.ml", 8, 15)

Question

Here is my code:

type 'a tree = Empty | N of 'a * 'a tree * 'a tree


let absolute x = 
    if x > 0 then x 
    else -x

let rec node = function 
    | N(_, Empty, Empty) -> 1
    | N(_, g, d) -> 1 + node g + node d

let rec balanced = function 
    | N(_, Empty, Empty) -> 0
    | N(_,g,d) when absolute (node g - node d) > 1 -> 1
    | N(_,g,d) when absolute (node g - node d) <= 1 -> balanced g + balanced d


let () = print_int (balanced (N ('x', N ('x', Empty, Empty),
  N ('x', N ('x', Empty, Empty), Empty))))

Then it's telling me:

Fatal error: exception Match_failure("main.ml", 8, 15)

I don't understand what does it mean and it doesn't seem to indicate where my mistake comes from.

Moreover I get the following warnings:

File "main.ml", line 8, characters 15-93:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Empty
File "main.ml", line 12, characters 19-190:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(N (_, Empty, N (_, _, _))|N (_, N (_, _, _), _)|Empty)
(However, some guarded clause may match this value.)

How can I get rid of this warning?

I mean according to me it doesn't mean anything to say that I am missing the case N(_,_,_), but this case is always handled, so why is the compiler telling me that this case is not matched?

Answer 1

Before taking a look at your runtime errors, it's better to look at your compiler output first (that is the warnings).

You have two warnings. The first one:

File "main.ml", line 8, characters 15-93:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Empty

Here it tells us that your pattern matching in the node function does not handle the Empty case. Just add a | Empty -> 0 to your pattern matching and you should be good (by the way, you won't need the incomplete Node (_,Empty,Empty) case anymore).

Now your second warning is a bit more tricky:

File "main.ml", line 12, characters 19-190:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
(N (_, Empty, N (_, _, _))|N (_, N (_, _, _), _)|Empty)
(However, some guarded clause may match this value.)

Here, it tells that several patterns are not matched, but that some values are guarded. And indeed the case N (_,_,_) is.

You can show the compiler that all N (_,_,_) are handled by removing the second when clause (that is, when absolute (node g - node d) <= 1). The pattern matching won't reach this point unless this clause is true so you can be sure it is. Also, you make sure you don't repeat the same computation twice this way. Note that in this pattern matching too, you did not handle the Empty case again. Do that.

Now let's take a look at your exception. It basically says "The pattern-matching at line 8 character 15 failed". That's your node function. Where you were warned that your pattern matching was incomplete. The lesson here is "don't ignore warnings, they're not bothersome, they're important".