Does a list contain alternating elements

Question

I'm trying to write a function which would check, if its elements are alternating.

Example of such a list would be: [1,2,1,2,1,2]

My attempt so far:

fun isAlternating(lst) = 
   case lst of
      [] => true
    | x::y::tail =>  if y <> x 
             then isAlternating(y::tail) 
             else false

When I try to test the method it raises the following exception:

uncaught exception Match [nonexhaustive match failure]

It seems I'm missing a pattern, but I don't know which one. Can someone help me with this?

Answer 1

You're missing the one-element list in the pattern match. This one should work. In the case of the one-list element, you should return true by definition.

fun isAlternating(lst) = 
   case lst of
      [] => true
      | x::nil => true
      | x::y::tail =>  if y <> x 
                        then isAlternating(y::tail) 
                        else false;

Answer 2

Being a little bit pedantic, note that according to your example and also to the name of your function you want to check whether a list contains alternating elements (i.e, only two different elements that take turns in their occurrences in the list). But this is not what your function (or @Diego Sevilla's for that matter) is computing. You are merely checking that no consecutive elements in the list are the same. Maybe you really wanted something like this:

fun is_alternating (x::(xs as _::y::_)) =
      if x = y then is_alternating xs else false
  | is_alternating _ = true;

Note how the order of patterns matters: either we have at least 3 elements (pattern: x::_::y_::) or otherwise (pattern: _) we match everything else (i.e., empty lists, singleton lists, and two-element lists). Also note how using x as pattern avoids to reconstruct structures that where already there.

As for what the function is doing:

• If there are at least 3 elements, check that the first and the third are the same and recursively repeat this check for the tail of the input list.
• Otherwise, the list contains at most two elements and thus is alternating.