Pattern matching in generic recursive function is not working

Learning
1

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)
2

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
3

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.

4

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