使用递归确定子集

Question

我正在尝试编写一个函数 subset，它接受两个列表并确定第一个列表的元素是否出现在第二个列表中。

当输入如下函数时，代码会编译为 GHCi，但不会运行（即卡住）：

subset [1,2] [1,2]

这是我的代码：

subset :: (Eq a) => [a] -> [a] -> Bool
subset [] ys = True
subset (x:xs) ys
 | elem x ys = subset (x:xs) ys
 | otherwise =  False

谢谢！

Answer 1

subset (x:xs) ys
 | elem x ys = subset (x:xs) ys
                   -- ^^^^^^ --

注意上面的递归调用并没有改变参数！这将导致无限递归。您想在进行递归调用之前删除 x。

Answer 2

让我们仔细看看您的代码片段：

subset (x:xs) ys
 | elem x ys = subset (x:xs) ys

如果 elem x ys 成立，这是完全合理的，你有

subset (x:xs) ys = subset (x:xs) ys

它不会减少任何参数，只是重新重复相同的调用。

因此，无限循环。

在处理布尔值时，习惯上使用逻辑连接词，这通常会导致更简洁明了的定义：

subset (x:xs) ys = elem x ys && subset ..... .....

就是你所需要的，因为 (&&) 的真相 table 是

    True  && x  =  x
    False && _  =  False

即当第一个参数为假时，甚至不检查第二个参数的值。

Answer 3

不需要显式递归；您可以使用 all 来验证 (`elem` ys) 对于 xs:

中的每个值都是正确的

subset xs ys = all (`elem` ys) xs

Determine subset using recursion