Haskell - 检查所有列表元素是否唯一

Question

我需要比较给定列表的所有元素是否唯一.(为了记录,我这样做是出于学术目的.)

这是我到目前为止:

allDifferent :: (Eq a) => [a] -> Bool
allDifferent list = case list of
    []      -> True
    (x:xs)  -> if x `elem` xs then False else allDifferent xs

这非常有效!

现在,当我尝试这样做时......

allDifferent2 :: (Eq a) => [a] -> Bool
allDifferent2 list
    | null list                                                     = True        
    | (head list) `elem` (tail list) || allDifferent2 (tail list)  = False
    | otherwise  

它只是没有按预期工作.我从GHCi得到以下输出:

*Main> allDifferent2 [1..4]
False
*Main> allDifferent2 [1..5]
True
*Main> allDifferent2 [1..6]
False
*Main> allDifferent2 [1..7]
True

即对于具有偶数元素的每个列表,它输出False,对于奇数量的元素,输出True.

我错过了什么？有人会照顾一些光吗？

Answer 1

另一种剥削方式notElem:

allDifferent :: (Eq a) => [a] -> Bool
allDifferent list = case list of
    []      -> True
    (x:xs)  -> x `notElem` xs && allDifferent xs

次要变体,直接在方程式中使用模式匹配:

allDifferent :: (Eq a) => [a] -> Bool
allDifferent []     = True
allDifferent (x:xs) = x `notElem` xs && allDifferent xs

我倾向于远离部分功能head,tail,所以基于守卫的变体看起来更糟糕.

Answer 2

我会以不同的方式做这件事。递归 +elem是O(n²)。或者，您可以先对列表进行排序，然后成对比较元素。这样排序是O(n?log n)，遍历O(n)。所以总体O(n?log n)：

import Data.List

allDifferent :: (Ord a, Eq a) => [a] -> Bool
allDifferent = comparePairwise.sort

comparePairwise :: Eq a => [a] -> Bool
comparePairwise [] = True
comparePairwise [_] = True
comparePairwise (x:y:xs) 
    | x == y = False
    | otherwise = comparePairwise (y : xs)