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. — sshine, Jul 24 '15 at 14:46

score 4 · Accepted Answer · answered Jul 22 '15 at 17:09

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 Answers1

Linked