另一个集合 SML 的集合子集

Question

我正在尝试实现另一个集合的集合子集。但是我无法使用以下示例 {{{}，1}} 和 {{1，{}}} 让它工作，我已经尝试了我能做的一切。我的主要目标是设置相等，在这种情况下返回 true。首先，我想让我的子集工作，然后实现设置的相等性。

 datatype expression = SET of expression list | TUPLE of expression list | INT of int    
fun member(a,SET y) = List.exists (fn x => x=a) y;
fun member1 (n,nil) = false
|   member1 (n, SET h::r) = (n=h) orelse member1 (n,r);
fun isIn value list = List.exists (fn x=>value=x) list;
 fun isSubset' ([],s') = true 
   | isSubset' (e::s,s') = isIn e s' andalso isSubset' (s,s');
 fun isSubset(SET s,SET s') = isSubset'(s,s');

 fun subsetEQ [] S' = true 
    | subsetEQ (x::xs) S' = isIn x S' andalso subsetEQ xs S';
      fun setEq (SET S,SET S') = (subsetEQ S S') andalso (subsetEQ S' S) ;

val x0 = INT 8;
val x1 = SET [SET[SET[],INT 1]];
val x2 = SET [SET[INT 1,SET[]]];
val x3 = setEq (x1,x2);

Answer 1

你所拥有的问题在于，

例如

fun isIn value list = List.exists (fn x=>value=x) list;

您使用的是正则相等，但对于嵌套集，您需要尝试定义的集合相等性的概念。

你真正需要的是三个相互递归的函数，一个用于成员资格，一个用于子集，一个用于相等。此外，与其Warning: match nonexhaustive大量烦人的消息，为什么不为所有模式提供合理的定义呢？以下代码修改是您可以做的事情(请注意关键字 and 而不是三个相互递归函数中的第二个和第三个的fun(：

datatype nested = SET of nested list | INT of int 
fun member (_, INT i) = false
|   member (SET x, SET y) = List.exists (fn z => equals(SET x, z)) y
|   member (INT i, SET y) = List.exists (fn x => x = INT i) y
and equals (INT i, INT j) = i = j
|   equals (INT i, SET y) = false
|   equals (SET x, INT j) = false
|   equals (SET x, SET y) = subset (SET x, SET y) andalso subset(SET y, SET x)
and subset (_, INT i) = false
|   subset (INT i, _) = false
|   subset (SET [], SET y) = true
|   subset (SET (x::xs), SET y) = member (x, SET y) andalso subset(SET xs, SET y);
val x0 = INT 8;
val x1 = SET [SET[SET[],INT 1]];
val x2 = SET [SET[INT 1,SET[]]];
val x3 = equals (x1,x2);

上面的编译没有警告，x3 = true.