对称关系递归SML

Question

在 ML isRelationSymmetric 中定义一个递归谓词，它接受关系 r（表示为元组列表），如果 r 对称则返回 true，否则返回 false。

这是我到目前为止所拥有的。

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

我只能检查前两个元素的对称性，但我需要检查其余的。

Answer 1

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

Answer 2

由于 @jwolf 似乎已经解决了这个问题，因此有一种利用 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;

但是，为了澄清，应该 [(1, 2), (2, 1), (2, 3), (3, 2), (3, 2)] 测试对称或不对称，因为有两个 (3, 2) 实例，而只有 1 个 (2, 3) 实例？

如果我们想抓住这一点，我们可以使用 List.filter 来查找我们正在考虑的对的任何反向，然后计算该列表的长度。该列表的长度应等于与当前匹配的对列表的长度。

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;