如何检查一个元素是否存在于haskell的列表中？

Question

我知道之前有人问过这个问题，但答案偏离了主要问题。

这是一个检查元素是否存在于 Haskell 中的方法

elem’ x (y : ys) = if x == y then True else elem’ x ys

我感到困惑的是，在 Haskell 中，(y : ys)这将 y 添加到 ys，那么此函数如何真正检查元素是否存在？因为我在这里没有看到任何循环，除了将相同的递归调用传递y给ys.

请赐教。

Answer 1

除了将相同的 y 传递给 ys 的递归调用之外，我在这里没有看到任何循环

递归部分将列表的尾部传递给elem'函数，而不是同一个列表。因此，一旦它到达列表的末尾，剩下的唯一尾部就是空列表，[]，它应该在另一个函数模式中终止，如下所示：

elem' _ [] = False

编辑：进一步澄清您的评论

您可以像这样描述递归调用：

-- assuming elem' is defined as:
elem' _ [] = False
elem' x (y : ys) = if x == y then True else elem' x ys

-- calling elem' trying to find 6 in [1..5]
elem' 6 (1 : [2, 3, 4, 5]) = if 6 == 1 then True else elem' 6 [2, 3, 4, 5]
elem' 6 (2 : [3, 4, 5])    = if 6 == 2 then True else elem' 6 [3, 4, 5]
elem' 6 (3 : [4, 5])       = if 6 == 3 then True else elem' 6 [4, 5]
elem' 6 (4 : [5])          = if 6 == 4 then True else elem' 6 [5]
elem' 6 (5 : [])           = if 6 == 5 then True else elem' 6 []
elem' 6 []                 = False