Recursive Anti-Symmetrical Counter SML

Question

This is an anti-symmetrical recursive function that will take a list of pairs If the list is anti-symmetrical then an empty list will return and if the list is symmetrical it will return only the two pairs that are symmetrical.

Here is an example output.

val antisymmetric_rel = [(1,2), (2,3), (4,4), (5,9), (10,9), (0,0)];

antisymmetricCounterEx(antisymmetric_rel);
(* [] *)

val not_antisymmetric_rel = [(1,2), (2,3), (4,4), (5,9), (10,9), (9,5)];
(* [((5,9),(9,5))] *)

Here is what I have so far.

  fun antisymmetricCounterEx([]) = [] 
    | antisymmetricCounterEx(relation) =
        let 
          fun testOne((a, b), []) = []
            | testOne((a, b), (c, d)::rest) =
                (if (not (a = d)) orelse testOne((b, d), rest) ) then []
                else [(a, b)] @ testOne((c, d), rest);

          fun testAll([]) = [] 
            | testAll((a, b)::rest) = 
                testOne((a, b), relation) @ testAll(rest);
        in 
          testAll(relation)
        end;

I am getting errors that I cannot understand but it seems that the type and operands are ok.

Answer 1

First off, let's clean up your code a bit.

1. We can remove the parentheses here: (if (not (a = d)) orelse testOne((b, d), rest) ) then [] which break the syntax, as well as generally eliminate extraneous parens throughout the code.
2. not (a = d) can be written as a <> d
3. [(a, b)] @ testOne((c, d), rest) is replaced with (a, b) :: testOne((c, d), rest)

fun antisymmetricCounterEx([]) = [] 
  | antisymmetricCounterEx(relation) =
    let 
      fun testOne((a, b), []) = []
        | testOne((a, b), (c, d)::rest) =
          if a <> d orelse testOne((b, d), rest)  then []
          else (a, b) :: testOne((c, d), rest);

      fun testAll([]) = [] 
        | testAll((a, b)::rest) = 
          testOne((a, b), relation) @ testAll(rest);
    in 
      testAll(relation)
    end;

This still fails because as pointed out in comments testOne returns a list:

fun testOne((a, b), []) = []

But it's used in a boolean context.

Really what you have is a filtering exercise. You need to filter for any pair that has a symmetrical counterpart in the list. However, you need to account for pairs that are symmetrical with themselves, like (4, 4) and (0, 0).

To aid with this, let's write a list_count function that can count the number of elements in a list that fulfill a predicate function.

fun list_count _ [] = 0
  | list_count f (x::xs) = 
    (if f x then 1 else 0) + list_count f xs;

We can now use List.filter and list_count to achieve the desired result.

fun sym_pairs(pairs) =
  List.filter 
    (fn (a, b) => 
       let
         val c = list_count (fn (c, d) => a = d andalso b = c) pairs 
       in
         if a = b then c > 1
         else c = 1
       end) 
    pairs;

Now:

sym_pairs([(1,2), (2,3), (4,4), (5,9), (10,9), (0,0)]);

Yields: []. And:

sym_pairs([(1,2), (2,3), (4,4), (5,9), (10,9), (9,5)]);

Yields: [(5, 9), (9,5)].