Syntax error: ')' expected, but I cannot find where

Question

Here is my code:

type noeud = Lettre of (char * bool * arbre_lex)
and arbre_lex = noeud list

exception Deja_defini of string



let rec ajoute mot arbre n =
    if existe mot arbre then raise (Deja_defini mot) else
    match arbre with
        | [] ->
            begin
                if n+1 = String.length mot then [ Lettre( mot.[n] , true , [] ) ]
                else [ Lettre ( mot.[n] , false, ajoute mot arbre (n+1) ) ]
            end
        | head::tail ->
            begin
                match head with 
                    | Lettre (mot.[n], b, a) -> (*line 19, source of error*)
                        begin
                            if n+1 = String.length mot then [ Lettre ( mot.[n] , true , a ) ]::tail 
                            else [ Lettre ( mot.[n] , b , ajoute mot a (n+1) ) ]::tail
                        end
                    | Lettre (_, b, a) -> ajoute mot tail n
            end

When compiling, I get the following error:

$ocamlc -o main *.ml
File "main.ml", line 19, characters 21-22:
Error: Syntax error: ')' expected
File "main.ml", line 19, characters 17-18:
Error: This '(' might be unmatched

Now I know I can improve my code, and I can include the second match in the first one, however, I'm specifically interested in finding the source of the error. I tried a lot of things, but none of them seemed to change the error.

So feel free to post improvements, but I'm mostly interested into how I can run this exact code to help avoid the error in the future.

Answer 1

The syntactic construct on the left side of the arrow is not an ordinary expression, but a pattern. For convenience it looks very much like an expression, but it behaves very differently. It is also purely a compile time construct.

For example, the pattern a, like in Lettre (_, b, a) will not evaluate to the value of a, or match the value at the position of a against the value of an existing binding named a. Instead it will make a new binding named a that refer to the value at the position of a, and shadow any previous binding of that name.

So if, for example, the value you are matching against is Lettre ('a', true, []), a will, on the right side of the arrow, refer to the value []. And b will refer to true.

Outside of being a convenient syntax for binding values to names in patterns, not allowing runtime values in patterns allows the compiler to make guarantees about the exhaustiveness of a pattern match as well as to optimize it at compile time. If runtime values were allowed in patterns you would always have to provide a wildcard pattern to catch the rest of the possibilities since you won't be able to know at compile time which possibilities might match at runtime.

I hope you see now why it doesn't make sense to allow expressions like mot.[n], or even a name bound to the value of mot.[n], in patterns.

However, there is a construct, separate from a pattern, that allows runtime conditions to be used in pattern matching, called "guards" or "when" clauses. Using your example:

match head with 
    | Lettre (ch, b, a) when ch = mot.[n] -> ...

This does require a case with a wildcard in place of ch to cover all the cases that the guard does not match. But since you already have that you should be good.