Having trouble creating exhaustive pattern matching SML

Question

I can't seem to figure out how to fully pattern-match this function. I want to check if a list is sorted using a function as an argument to say which order (inc or dec, < or >). I think my base code is pretty much there, but I am getting an error for: Uncaught SML exception: Match.

fun checkifsorted f =
  fn nil     => false
   | []      => true
   | a::b::c =>
     if f(a, b) then checkifsorted f (b::c)
     else false;

is_sorted (op >) [7,5,2,1];

If someone could point me to what I am missing in my pattern-matching section, it would be truly appreciated!

Answer 1

A quibble

You pattern match on both nil and []. This is the same pattern.

The problem

You then provide the pattern a::b::c which matches a list with two or more elements. Eventually you will call your function with a list with a single element, and the incomplete pattern match will surface.

Consider calling: checkifsorted op< [1, 2, 3, 4, 5, 6]

checkifsorted op< [1, 2, 3, 4, 5, 6]
  op<(1, 2)
checkifsorted op< [2, 3, 4, 5, 6]
  op<(2, 3)
checkifsorted op< [3, 4, 5, 6]
  op<(3, 4)
checkifsorted op< [4, 5, 6]
  op<(4, 5)
checkifsorted op< [5, 6]
  op<(5, 6)
checkifsorted op< [6]
  ! no match

Cleaning up your code

You can clean this up a bit by not using fn and just putting both parameters in the function definition and pattern-matching on them. I've also used as to bind tl to the entire tail of the list, and _ instead of f in the case where it is irrelevant to the outcome.

fun checkifsorted _ [] = true
  | checkifsorted f (a::(tl as b::c)) =
      if f(a, b) then checkifsorted f tl
      else false;

A solution

A list with a single element must be sorted, no? Presumably yes, so we can add a pattern in there to handle the single element list.

fun checkifsorted _ [] = true
  | checkifsorted _ [_] = true
  | checkifsorted f (a::(tl as b::c)) =
      if f(a, b) then checkifsorted f tl
      else false;