# Pattern matching in generic recursive function is not working

I was writing a generic power function a^b.
This function uses recursion and in its plain integer version the pattern matching works,
but not in a generic module.
Can somebody explain me why I can’t use pattern matching in this code?

``````module type Tt = sig
type t

val zero : t
val one : t
val ( * ) : t -> t -> t
val ( - ) : t -> t -> t
end

module Expt (M : Tt) = struct
type tt = M.t
let zero = M.zero
let one = M.one
let ( * ) = M.( * )
let ( - ) = M.( - )

let expt (a:tt) (b:tt) =
let rec expt' (acc:tt) (a:tt) (b:tt) : tt=

if zero = b then  (acc * one)
else if one = b  then (acc * a)
else  expt' (acc * a) a (b - one) in

(* This does not work - Compiler says unused variables zero,...*)
(*match b with
| zero -> (acc * one)
| one -> (acc * a)
| _ -> expt' (acc * a) a (b - one) in*)

expt' one a b
end

module IntExpt : Tt with type t = int = struct
type t = int

let zero = 0
let one = 1
let ( * ) = Stdlib.( * )
let ( - ) = Stdlib.( - )
end

module ExptInt = Expt(IntExpt)
``````

When a value name appears in pattern-matching, it binds the matched value to that name. So `match b with zero` is essentially the same as `let zero = b`.

More generally, you can’t pattern-match with an abstract type, because pattern-matching requires knowledge of the type’s definition.

2 Likes

I see - This explains why this is also not working:

``````match b with
| zero when b = zero -> (acc * one)
| one when b = one -> (acc * a)
| _ -> expt' (acc * a) a (b - one)
``````

This produces no compiler error, but it compute wrong - always one.

Indeed, `when` guards tend to prevent the compiler from identifying unused cases because it is not able to analyze how a guard will evaluate. Your example will work as expected if you don’t bind `zero` or `one`:

``````match b with
| _ when b = zero -> (acc * one)
| _ when b = one -> (acc * a)
| _ -> expt' (acc * a) a (b - one)
``````

But at that point, you might as well just use `if` instead of `match`.

1 Like