测试列表是否具有重复(重复)元素的 Haskell 函数

Question

我有一个练习要做，但是由于我是这门语言的新手，我找不到任何方法来做这件事。

我有这个定义为“重复”的功能，在本段中给出。它接收一个 Int 列表并返回一个 Bool 值。它应该检查列表是否有任何重复的元素。如果是，则为真，否则为假。还有一个额外的:我必须通过递归来定义函数，所以它必须是递归函数。将不胜感激任何帮助。

repeated :: [Int] -> Bool

EDIT1:到目前为止，我只成功使用了这么多的代码

repeated :: [Int] -> Bool
repeated [] = False
repeated (h:t) = 

这只给了我空列表。其他的，到现在还想不通……

EDIT2:忘记了单数列表......另外，可能的答案？

repeated :: [Int] -> Bool
repeated [] = False
repeated [_] = False
repeated (h:t) = if elem h t then True
                             else repeated t

差不多就是这样。我已经编译了 .hs 并且效果很好。谢谢大家的建议和提示! :)

Answer 1

您想查找列表是否有任何重复项。这意味着您必须跟上您已经访问过的元素列表，以便您可以检查它。因此，首先，编写一个函数来检查单个元素是否存在于已访问值的列表中:

alreadyVisited :: Int -> [Int] -> Bool
alreadyVisited x [] = False
alreadyVisited x (v:visited) = ???

(注意:这在 Prelude 中称为 elem，但您应该能够自己实现它，这是一个很好的做法)

然后，您将要编写循环遍历目标列表中所有元素的 main 函数，构建一组已访问的元素，直到找到重复项。一旦找到重复项，该函数可以退出而不检查列表的其余部分。

-- Using a helper hides the fact that the visited list is needed
repeated :: [Int] -> Bool
repeated xs = go xs []
--                   ^--  initial visited list is empty
    where
        -- same base case that you came up with,
        -- an empty list does not have duplicate elements
        go [] _ = False
        -- The recursive step, think about what you need this function to do
        go (x:xs) visited =
            if alreadyVisited x visited
                then ???        -- If it's already visited, do what?
                else ???        -- Otherwise?

这里我只是为你设置了结构，你必须自己填写细节。请记住，这不是一个有效的实现，尤其是因为 alreadyVisited 的速度太慢了。将变为 visited大小会增加，但如果您对速度感兴趣，那么您可以将访问列表换成 Data.Set.Set ，它有更好的查找时间。