对称关系递归 SML

Question

在 ML isRelationSymmetric 中定义一个递归谓词，它接受关系 r（表示为元组列表）并且 returns 如果 r 是对称的则为真，否则为假。

这是我目前的情况。

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) 有两个实例而 (2, 3) 只有 1 个实例？

如果我们想抓住这一点，我们可以使用 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;

对称关系递归 SML

Symmetric Relation Recursive SML

recursion

sml

ml

symmetry