递归反对称计数器SML

Question

这是一个反对称递归函数，它将获取一个对列表。如果列表是反对称的，则将返回一个空列表，如果列表是对称的，它将只返回对称的两对。

以下是输出示例。

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))] *)

这是我迄今为止所拥有的。

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;

我收到了一些我无法理解的错误，但类型和操作数似乎还可以。

Answer 1

首先，让我们稍微清理一下您的代码。

1. 我们可以删除这里的括号：(if (not (a = d)) orelse testOne((b, d), rest) ) then []，它破坏了语法，并且通常在整个代码中删除无关的paren
2. not (a = d)可以写成a <> d
3. [(a, b)] @ testOne((c, d), rest)替换为(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;

这仍然失败，因为正如评论中所指出的，testOne返回一个列表：

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

但它是在布尔上下文中使用的。

你真正拥有的是一个过滤练习。您需要筛选列表中具有对称对应项的任何一对。但是，您需要考虑与自身对称的对，如(4, 4)和(0, 0)。

为了帮助实现这一点，让我们编写一个list_count函数，它可以计算列表中实现谓词函数的元素数量。

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

我们现在可以使用List.filter和list_count来实现期望的结果。

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;

现在：

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

产量：[]。和：

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

产量：[(5, 9), (9,5)]。