How do variables in pattern matching allow parameter omission?

Question

I'm doing some homework but I've been stuck for hours on something. I'm sure it's really trivial but I still can't wrap my head around it after digging through the all documentation available. Can anybody give me a hand? Basically, the exercise in OCaml programming asks to define the function x^n with the exponentiation by squaring algorithm.

I've looked at the solution:

   let rec exp x = function
    0 -> 1
   | n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
   | n when n mod 2 <> 0 -> let y = exp x ((n-1)/2) in y*y*x
   ;;

What I don't understand in particular is how the parameter n can be omitted from the fun statement and why should it be used as a variable for a match with x, which has no apparent link with the definition of exponentiation by squaring.

Here's how I would do it:

   let rec exp x n = match n with
   0 -> 1
   | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
   | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
   ;;

Answer 1

Your version is syntaxically correct, yields a good answer, but is long to execute. In your code, exp is called recursively twice, thus yielding twice as much computation, each call yielding itself twice as much computation, etc. down to n=0. In the solution, exp is called only once, the result is storred in the variable y, then y is squared.

Now, about the syntax,

let f n = match n with
  | 0 -> 0
  | foo -> foo-1

is equivalent to:

let f = function
  | 0 -> 0
  | foo -> foo-1

The line let rec exp x = function is the begging of a function that takes two arguments: x, and an unnammed argument used in the pattern matching. In the pattern matching, the line

 | n when n mod 2 = 0  ->

names this argument n. Not that a different name could be used in each case of the pattern matching (even if that would be less clear):

| n when n mod 2 = 0  -> let y = exp x (n/2) in y*y
| p when p mod 2 <> 0 -> let y = exp x ((p-1)/2) in y*y*x

Answer 2

The keyword "function" is not a syntaxic sugar for

match x with

but for

fun x -> match x with

thus

let rec exp x = function

could be replaced by

let rec exp x = fun y -> match y with

which is of course equivalent with your solution

let rec exp x y = match y with

Note that i wrote "y" and not "n" to avoid confusion. The n variable introduced after the match is a new variable, which is only related to the function parameter because it match it. For instance, instead of

let y = x in ...

you could write :

match x with y -> ...

In this match expression, the "y" expression is the "pattern" matched. And like any pattern, it binds its variables (here y) with the value matched. (here the value of x) And like any pattern, the variables in the pattern are new variables, which may shadow previously defined variables. In your code :

let rec exp x n = match n with
  0 -> 1
  | n when (n mod 2) = 1 -> (exp x ((n-1)/2)) * (exp x ((n-1)/2)) * x
  | n when (n mod 2) = 0 -> (exp x (n/2)) * (exp x (n/2))
;;

the variable n in the two cases shadow the parameter n. This isn't a problem, though, since the two variable with the same name have the same value.