查找列表中的第一个重复元素

Question

我对 Haskell 很陌生。我正在尝试在 Haskell 中编写代码来查找列表中的第一个重复元素，如果它没有重复元素，则不会给出重复的消息。我知道我可以通过 nub 函数来做到这一点，但我试图在没有它的情况下做到这一点。

Answer 1

这是一种方法：

import qualified Data.Set as Set

dup :: Ord a => [a] -> Maybe a
dup xs = dup' xs Set.empty
  where dup' [] _ = Nothing
        dup' (x:xs) s = if Set.member x s 
                           then Just x
                           else dup' xs (Set.insert x s)

dupString :: (Ord a, Show a) => [a] -> [Char]
dupString x = case dup x of
                  Just x  -> "First duplicate: " ++ (show x)
                  Nothing -> "No duplicates"

main :: IO ()
main = do
       putStrLn $ dupString [1,2,3,4,5]
       putStrLn $ dupString [1,2,1,2,3]
       putStrLn $ dupString "HELLO WORLD"

它的工作原理如下：

*Main> main
No duplicates
First duplicate: 1
First duplicate: 'L'

Answer 2

这不是您的最终答案，因为当一个元素被重复多次而不是立即返回时，它会做不必要的工作，但它说明了您如何系统地运行所有可能性（即“列表中的这个元素是否有在列表的下方重复吗？”）

dupwonub :: Eq a => [a] -> [a]
dupwonub [] = []
dupwonub (x:xs) = case [ y | y <- xs, y == x ] of
                    (y:ys) -> [y]
                    []     -> dupwonub xs

Answer 3

如果您仍在研究 Haskell，我想您可能会喜欢一个更快但更复杂的解决方案。它的运行时间为 O(n) （我认为），但对列表的类型有稍微严格的限制，即必须是 Ix 类型。

AccumArray 是一个非常有用的函数，如果您还没有的话，强烈建议您研究一下。

import Data.Array

data Occurances = None | First | Duplicated
                deriving Eq

update :: Occurances -> a -> Occurances
update None _ = First
update First _ = Duplicated
update Duplicated _ = Duplicated

firstDup :: (Ix a) => [a] -> a
firstDup xs = fst . first ((== Duplicated).snd) $ (map g xs)
  where dupChecker = accumArray update None (minimum xs,maximum xs) (zip xs (repeat ()))
        g x = (x, dupChecker ! x)

first :: (a -> Bool) -> [a] -> a
first _ [] = error "No duplicates master"
first f (x:xs) = if f x
                 then x
                 else first f xs

不过请注意，（最小 xs，最大 xs） 大小的数组可能会真正增加您的空间需求。