使用map、foldr或foldl函数的SML集合交集

Question

我正在为课堂做 SML 编程作业，但遇到了一个问题。问题是： “编写一个使用map、foldr或foldl来计算非空集合列表的交集的ML函数。在这里，您可以假设集合表示为列表。对于这个问题，您可以使用辅助命名函数（例如，isMember）提示：非空集合列表至少包含一个集合。”

这就是我到目前为止所拥有的，任何人都可以为我指明正确的方向吗？我对 SML 还很陌生？

fun member(x,[]) = false
|   member(x,L) =
        if x=hd(L) then true
        else member(x,tl(L));

fun intersect(L1,L2) = if tl(L1) = [] then L1 
else if member(hd(L1),L2) = true then L1
else intersect(tl(L1),L2);

fun combine(L1) = if tl(L1) = [] then hd(L1)
else
    foldr intersect [] L1;

我希望代码执行的操作是首先执行具有列表列表的组合函数。它检查是否只有一个列表（即 tl(L1) = []），如果为真，则仅打印第一个列表。如果它为假，我想调用foldr函数，然后调用intersect函数。理论上，在foldr函数期间，我希望它检查第一个列表和第二个列表，并且只保留相同的值，然后检查下一个列表到那些保留的值，并继续执行此操作，直到检查完每个列表为止。完成后，我希望它打印每个列表中的每个值（即集合的交集）。

我知道我的成员函数可以工作，并且组合函数可以执行其应该执行的操作，我的问题是，交集函数有什么问题，有人可以解释交集应该做什么吗？

我显然不想要直接的答案，这不是我来这里的目的。我需要帮助才能找到正确答案。

Answer 1

您的 member 和 combine 函数看起来不错，但您需要更仔细地考虑 intersect 函数。对于初学者来说，如果 L1 是空列表，则会引发异常，因为 tl 不对空列表进行操作。想想你需要担心的三种情况：

• L1 is nil
• hd(L1) is in L2
• hd(L1)< /code> 不在 L2 中

找出每种情况下您需要做什么，然后从那里开始。

Answer 2

这是我的工作答案！

fun member(x,[]) = false
|   member(x,L) =
        if x=hd(L) then true
        else member(x,tl(L));       

fun intersect([],[]) = []
| intersect(L1,[]) = []
| intersect(L1,L2) = if member(hd(L2), L1) then hd(L2)::intersect(L1, tl(L2))
    else intersect(L1, tl(L2));

fun combine(L1) = if L1 = [] then []
else if tl(L1) = [] then hd(L1)
else foldr intersect (hd(L1)) (tl(L1));

这是运行的一些测试用例。

combine([[1,2],[1,3],[1,4]]);
val it = [1] : int list
combine([[1,2,3],[1,8,9,3],[1,4,3,8,9]]);
val it = [1,3] : int list
combine([[1,2,3,8,9],[1,8,9,3],[1,4,3,8,9]]);
val it = [1,3,8,9] : int list