OCaml function parameter pattern matching for strings

Question

I tried to pass a string in to get a reversed string. Why can't I do this:

let rec reverse x = 
  match x with
  | "" -> ""
  | e ^ s -> (reverse s) ^ e;;

The compiler says it's a syntax error. Can't I use ^ to destructure parameters?

Answer 1

When you write a pattern matching expression, you cannot use arbitrary functions in your patterns. You can only use constructors, which look like unevaluated functions. For example, the function "+" is defined on integers. So the expression 1+2 is evaluated and gives 3; the function "+" is evaluated, so you cannot match on x+y. Here is an attempt to define a function on natural numbers that checks whether the number is zero:

 let f x =  match x with
  | 0 -> false
  | a+1 -> true
 ;;

This cannot work! For the same reason, your example with strings cannot work. The function "^" is evaluated on strings, it is not a constructor.

The matching on x+1 would work only if numbers were unevaluated symbolic expressions made out of the unevaluated operator + and a symbolic constant 1. This is not the case in OCAML. Integers are implemented directly through machine numbers.

When you match a variant type, you match on constructors, which are unevaluated expressions. For example:

 # let f x = match x with
    | Some x -> x+1
    | None -> 0
 ;;
 val f : int option -> int = <fun>

This works because the 'a option type is made out of a symbolic expression, such as Some x. Here, Some is not a function that is evaluated and gives some other value, but rather a "constructor", which you can think of as a function that is never evaluated. The expression Some 3 is not evaluated any further; it remains as it is. It is only on such functions that you can pattern-match.

Lists are also symbolic, unevaluated expressions built out of constructors; the constructor is ::. The result of x :: y :: [] is an unevaluated expression, which is represented by the list [x;y] only for cosmetic convenience. For this reason, you can pattern-match on lists.