Standard ML: Operator and Operand Don't Agree (Circularity)

Question

I'm trying to write a function in SML to flip alternate elements of a list. Here's my function:

 fun flipAlternate(nil) = nil
     | flipAlternate([x]) = x
     | flipAlternate(x::y::xs) = y::x::flipAlternate(xs);

When I go to use my file (Ullman.sml) in the interactive interpreter, I get this compilation error:

- use "Ullman.sml";
[opening Ullman.sml]
Ullman.sml:5.31-5.54 Error: operator and operand don't agree [circularity]
  operator domain: 'Z list * 'Z list list
  operand:         'Z list * 'Z list
  in expression:
    x :: flipAlternate xs

So SML is saying it requires a list of lists of integers but I'm only giving it a pair of lists of integers?

I'm a bit lost here so any help would be much appreciated.

Thanks, bclayman

The first case says flipAlternate([]) = [], and from this we can infer that its type must be 'a list -> 'a list. The second case says flipAlternate([x]) = x, and from this we can infer that its type must also be 'a list -> 'a. Both can only be true if 'a is set to 'a list, but then it must also have the type 'a list list -> 'a list. This leads to infinite regression, but SML's type unifier complains long before that as such types are not allowed. — Simon Shine

Jonathan Cast Jonathan Cast · Accepted Answer · 2015-07-22T17:09:36

Your second case is wrong; you want

fun flipAlternate(nil) = nil
 | flipAlternate([x]) = [x]
 | flipAlternate(x::y::xs) = y::x::flipAlternate(xs);

SML is looking at the second case and concluding

flipAlternate :: 'z list list -> 'z list

which isn't compatible with the recursion in your third case.

Edit: It knows the result is a list from the first case, and concludes the argument has one more list than the result from the second case.

Standard ML: Operator and Operand Don't Agree (Circularity)

1 Answers