Symmetric Relation Recursive SML-CodePudding

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.

CodePudding user response：

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);

CodePudding user response：

As @jwolf appears to have solved this, an alternative approach taking advantage of List.exists.

fun sym(relation) =
  let
    fun sym'([]) = true
      | sym'((a, b)::rest) = 
          List.exists (fn (c, d) => a = d andalso b = c) relation 
          andalso sym'(rest)
  in
    sym'(relation)
  end;

However, for clarification, should [(1, 2), (2, 1), (2, 3), (3, 2), (3, 2)] test as symmetric, or not, as there are two instances of (3, 2) and only 1 of (2, 3)?

If we want to catch this, we can use List.filter to find any reverses of the pair we're considering, and then calculate the length of that list. The length of that list should be equal to the length of the list of pairs matching the current one.

fun sym(relation) =
  let
    fun sym'([]) = true
      | sym'((a, b)::rest) = 
          let
            val len  = List.length(List.filter (fn (c, d) => a = d andalso b = c) relation)
            val len' = List.length(List.filter (fn (c, d) => a = c andalso b = d) relation)
          in
            len = len' andalso sym'(rest)
          end
  in
    sym'(relation)
  end;