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

Question

我有一个练习要做,然而由于我是这门语言的新手,我找不到任何方法可以做到这一点.

我有这个"重复"的功能,这个功能是根据本段给出的.它接收一个Int列表并返回一个Bool值.它应该检查列表是否有任何重复的元素.如果是这样,它是真的,如果不是,那就是假的.还有一个额外的:我必须通过递归来定义函数,所以它必须是递归函数.非常感谢任何帮助.

repeated :: [Int] -> Bool

编辑1:到目前为止,我只是成功地使用了这么多代码

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

这让我回到空列表中.其余的,到目前为止我还没弄清楚......

编辑2:忘了单数列表......还有,可能的答案？

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

这就是它.我已经编译了.hs并且它工作得很好.谢谢大家的建议和提示!:)

Answer 1

这是我的方法（使用集合和比较长度）

import qualified Data.Set as Set -- From the 'containers' library

hasDuplicates :: (Ord a) => [a] -> Bool
hasDuplicates list = length list /= length set
  where set = Set.fromList list

我正在使用容器 Haskell Package。

Answer 2

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

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

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

然后,您将要编写循环遍历目标列表中所有元素的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,但如果您对速度感兴趣,那么您可以将访问列表替换为a Data.Set.Set,其具有更好的查找时间.