Warning: match nonexhaustive

Question

I wrote some sml code with all the base cases I can think of, however i still get this warning. Thus function checks if the first list is a permutation of the second list. Im not sure if it works though i think its entering an infinite loop!

fun isPermutation(nil: int list, nil: int list): bool = true
  | isPermutation(x::nil, nil) = false
  | isPermutation(nil, y::nil) = false
  | isPermutation(x1::nil, x2::nil) = if (x1=x2) then true else false
  | isPermutation(x1::l1, x2::l2) = isPermutation(x1::nil, x2::l2) andalso isPermutation(l1, x2::l2)

Answer 1

So these are the cases you have:

(nil, nil)
(x::nil, nil)
(nil, y::nil)
(x1::nil, x2::nil)
(x1::l1, x2::l2)

However, if (x,y) is ([], [1,2,3]), the function matches none of these cases. This is because in the lines (x::nil, nil) and (nil, y::nil), you assume that if one of the arguments is nil, the other one should be a singleton list (a list containing only one element). If you use (_, nil) and (nil, _) in those cases, you would cover other possible lists that are not singleton, which would eliminate the nonexhaustive match warning.

Note that _ is just a wildcard in the pattern that doesn't create a new value binding, since you can just use x or y to access the tuple element in the position of the wildcard.