recursionsmlmlsymmetry

Symmetric Relation Recursive SML


Define a recursive predicate in ML isRelationSymmetric that accepts a relation r (represented as a list of tuples) and returns true if r is symmetric and false otherwise.

Here is what I have so far.

fun isRelationSymmetric([]) = false
  | isRelationSymmetric((a,b)::rest) = 


val x = [(1,2),(2,1),(2,3),(3,2)]; //suppose to come out true
val y = [(1,1),(1,3)];             //suppose to come out false 
val z = [(1,2),(2,1),(1,3)];       //suppose to come out false
isRelationSymmetric(x);
isRelationSymmetric(y);
isRelationSymmetric(z);

I was only able to check for symmetry for the first two elements but I need to check the rest.


Solution

  • fun isRelationSymmetric(relation) =
      let 
        fun testOne((a, b), []) = false
          | testOne((a, b), (c, d)::rest) =
              (b = c) andalso (a = d) orelse testOne((a, b), rest);
       
        fun test([]) = true
          | test((a,b)::rest) = testOne((a, b), relation) andalso test(rest);
      in
        test(relation)
      end;
    
    (* Test cases *)
    val x = [(1, 2), (2, 1), (2, 3), (3, 2)]; (* true *)
    isRelationSymmetric(x);
    
    val y = [(1, 1), (2, 3)]; (* false *)
    isRelationSymmetric(y);
    
    val z = [(1, 2), (2, 1)]; (* true *)
    isRelationSymmetric(z);