circularity error ML

[DarkLightning7]

I'm attempting to write a substitution function but am having trouble figuring out how to fix the Error:

operator and operand don't agree [circularity]
  operator domain: ''Z list * ''Z list * ''Z list
  operand:         ''Z list * ''Z list * ''Z
  in expression:
    sub2 (x,y,hd z)

Code:

fun sub2(x, y, z) = (
    case z of nil =>nil 
    | Int => if(x = z) then y else z 
    | List => (sub2(x, y, (hd z))) :: (sub2(x, y, (tl z)))
);

Any help understanding what is causing this and how to fix it is greatly apreciated.

[sepp2k]

The error is because you call sub2 first with hd z and then with tl z as the third argument. hd z and tl z have different types: If z is a list of foos, then hd z is a foo and tl z is a foo list. For foo and foo list to be the same type, foo has to be equal to foo list, which is impossible. That's the circularity the error message is complaining about.

Another error (not mentioned by the error message) is that the types of your patterns don't match: Your first pattern is nil, implying that z is a list (which it certainly is since you use hd and tl on it later). However your other two patterns are of some other type.

[DarkLightning7]

Thanks for the reply.
I was attepmting to check if z is a number but it appears that z must be the same type thoughout the function so I created a new datatype.

Here is the new code:

datatype n =Int of int | Real of real ;
datatype Cons = List of Cons*Cons  | Number of n | Null ;

fun sub2(x, y, z) = (
    case z of Null =>nil 
        | Number(x1) => if(x = z) then y else z 
        | (Cons(x1), Cons(x2)) => Cons((sub2(x, y, x1)), (sub2(x, y, x2)))
);

sub2(3,5,Cons(Number(3),Number(5)));
sub2(3,5,Cons(Cons(Number(3),Null),Number(1)));

I'm not quite sure what is wrong with it now. I get these errors I guess i realy dont understand pattern matching.

stdIn:32.20-32.27 Error: non-constructor applied to argument in pattern: Cons
stdIn:32.10-32.17 Error: non-constructor applied to argument in pattern: Cons
stdIn:32.33-32.37 Error: unbound variable or constructor: Cons
stdIn:32.68-32.70 Error: unbound variable or constructor: x2
stdIn:32.50-32.52 Error: unbound variable or constructor: x1
stdIn:30.3-32.73 Error: types of rules don't agree [tycon mismatch]
  earlier rule(s): Cons -> _ list
  this rule: 'Z * 'Y -> _
  in rule:
    (_,_) => <errorvar> (sub2 (<exp>,<exp>,<exp>),sub2 (<exp>,<exp>,<exp>))
stdIn:30.3-32.73 Error: case object and rules don't agree [tycon mismatch]
  rule domain: Cons
  object: _ list
  in expression:
    (case z
      of Null => nil
       | Number x1 => if x = z then y else z
       | (_,_) => <errorvar> (sub2 <exp>,sub2 <exp>))

The help is apreciated, Thanks

[DarkLightning7]

If you could tell me what (Cons(x1), Cons(x2)) should be inorder to extract the first segment and last segment from a Cons and explain why it is that, that would be great.

Thanks

[sepp2k]

Cons is just the name of your type - you do not have a constructor named Cons. So writing Cons(something) doesn't work. You probably meant List(x1, x2).

[DarkLightning7]

Ok that makes sense. Hopefully last question for this function
Here is the change Made to the above code:

| List(x1, x2) => List((sub2(x, y, x1)), (sub2(x, y, x2)))

Now I'm getting:

stdIn:32.31-32.45 Error: operator and operand don't agree [tycon mismatch]
  operator domain: ''Z list * ''Z list * ''Z list
  operand:         ''Z list * ''Z list * Cons
  in expression:
    sub2 (x,y,x1)
stdIn:32.49-32.63 Error: operator and operand don't agree [tycon mismatch]
  operator domain: ''Z list * ''Z list * ''Z list
  operand:         ''Z list * ''Z list * Cons
  in expression:
    sub2 (x,y,x2)
stdIn:30.3-32.65 Error: types of rules don't agree [tycon mismatch]
  earlier rule(s): Cons -> ''Z list
  this rule: Cons -> Cons
  in rule:
    List (x1,x2) => List (sub2 (<exp>,<exp>,<exp>),sub2 (<exp>,<exp>,<exp>))
stdIn:30.3-32.65 Error: case object and rules don't agree [tycon mismatch]
  rule domain: Cons
  object: ''Z list
  in expression:
    (case z
      of Null => nil
       | Number x1 => if x = z then y else z
       | List (x1,x2) => List (sub2 <exp>,sub2 <exp>))

I understand the basic cause of the first and second error I'm calling sub2 on (list, list, cons) when it takse (list, list, list) as arguments but I'm realy out of ideas as to how to fix it.

The third and forth errors I realy dont understand though.

[sepp2k]

The third error is telling you that the first two branches of your case return a list (nil or y/z respectively) while the third branch returns a Cons.

And the fourth error tells you that z is a list, but you treat it as a Cons.

The reason that it thinks that z is a list is because you do x=z, meaning x and z need to have the same type and then y else z, meaning y and z also need to have the same type.

To fix this, you should first decide what each of the arguments' types should actually be and what you want the function to return. Once you decided that, you can go through the code to find the places where each value is used with a type other than the one it should have and fix those.

[DarkLightning7]

Thanks. That makes a lot of sense. Here is my final product which actualy comiles and produces the desired results. I decided on a recursive type Cons because of the simplification of the final code it also allows me to construct a cons type which is what I wanted to begin with.

datatype Cons = Cons of Cons*Cons  | Number of int | Null ;

fun sub2(x, y, z) = (
    case z:Cons of Null =>Null 
        | Number(x1) => if(x = x1) then Number(y) else Number(x1) 
        | Cons(x1, x2) => Cons((sub2(x, y, x1)), (sub2(x, y, x2)))
);

Thanks again for all the help.