查找列表的子集

Question

我正在用 SML 编写一个函数来查找两个整数集的子集。例如，subset([1,5],[1,3,5]) 应该 return true。我在编写这个函数时遇到了一些麻烦。我的问题是我应该如何递归地写这个。这是我的功能：

fun subset(lst1,lst2) = true
  |  subset(a::;lst1,lst2) =
       if member(a,lst2) then subset(lst1,lst2)
       else false;

Answer 1

好的，根据评论，您似乎想要一个谓词，如果列表中的任何一个是另一个列表的子集，则该谓词为真。

这很难同时完成；同时递归两个列表会很快变得复杂。

相反，当且仅当 lst1 是 lst2.

的子集时，让我们修复您的代码并使其为真

然后我们就可以用它来实现我们想要的功能了：

fun either_subset(xs, ys) = subset(xs, ys) orelse subset(ys, xs)

您的第一个模式匹配所有对，模式匹配按照写入的顺序尝试，因此结果总是 true。
您可以通过两种方式解决此问题；要么让第一种情况更具体，只匹配空列表，

fun subset([],lst2) = true

或重新排列子句，使第一种情况匹配任何非空列表，

fun subset(a::lst1,lst2) =
       if member(a,lst2) then subset(lst1,lst2)
       else false
  | subset(lst1,lst2) = true

你也可以简化这个 - if e1 then e2 else false 等同于 e1 andalso e2，当你不使用模式的名称时，你可以使用通配符模式 _:

fun subset(x::xs, ys) = member(x, ys) andalso subset(xs, ys)
  | subset _ = true

或

fun subset ([], _) = true
  | subset (x::xs, ys) = member(x, ys) andalso subset(xs, ys)

Find the subset of a list