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

试试这个：

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

如果列表是 [] 你应该 return 正确（正如@bheklilr 所说:)）

如果列表不为空，您可以验证第一个元素是否在列表的尾部。如果是，return 错误。好的

但是当你说 "if it is in the tail of the list OR allDifferent2 (tail list)" 时，你正在终止你的功能。 "If all the elements are different in this list, return FALSE"，这不是你想要的。

编辑： 是的，@Luis。我通过将 "otherwise" 放在那里来解决这个问题。当我将守卫放在 allDifferent2（尾列表）之前时，它会检查此函数是否 returned True。因此它适用于 [1, 1, 2] （我的测试用例）但不适用于 [1, 2, 2] （类似于您的情况）。

Answer 2

另一种利用 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 3

我会以不同的方式来做这件事。递归 + 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)

Answer 4

我能想到的最简单合理的惯用方法是

allDifferent :: Ord a => [a] -> Bool
allDifferent = pairwiseDifferent . sort

pairwiseDifferent :: Eq a => [a] -> Bool
pairwiseDifferent xs = and $ zipWith (/=) xs (drop 1 xs)

为了有趣的折叠，

import Data.Maybe

pairwiseDifferent xs = foldr go (const True) xs Nothing
  where
    go x k Nothing = k (Just x)
    go x k (Just prev) = x /= prev && k (Just x)

另一种选择是使用 Set（某些严格性注释实际上可能不是必需的）：

import qualified Data.Set as S

allDifferent xs = foldr go (\s -> s `seq` True) xs S.empty
  where
    go x k s
       | S.member x s = False
       | otherwise = k $! S.insert x s

Answer 5

您可以依赖库函数：allDifferent xs = nub xs == xs。

或者，用无点表示法写成：allDifferent = uncurry (==) . (nub &&& id)。

使用 Data.Discrimination.nub，这发生在 O(n) 时间。

Answer 6

对列表进行排序，group runs of equal elements together, and check if all组只有一个元素。

import Data.List (group, sort)

pairwiseDistinct :: Ord a => [a] -> Bool
pairwiseDistinct xs = all (\ys -> null (tail ys)) (group (sort xs))

免积分版本：

pairwiseDistinct = all (null . tail) . group . sort

这假设对于任何两个元素 x 和 y，x == y 当且仅当 compare x y == EQ.

tail 在这里很好，因为 none 的组永远是空的，但如果你不喜欢部分函数，你可以替换 drop 1。

Answer 7

allDifferent []    = True
allDifferent (h:t) = 
                     let (e,(l,r)) = segment h t 
                     in e && allDifferent l && allDifferent r

segment p []     = (True,([],[])))
segment p (h:s) 
   | p > h       = let (e,(l,r)) = segment p s in (e,(l,h:r))
   | p < h       = let (e,(l,r)) = segment p s in (e,(h:l,r))
   | otherwise   = (False,([],[])))

如您所见，此解决方案的结构与快速排序非常相似。它作为中间数据结构共享一个二叉树，因此，时间复杂度非常相似。

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

Haskell - Checking if all list elements are unique

list

functional-programming

comparison