Haskell - checking the uniqueness of all elements of a list
I need to compare if all elements of a given list are unique. (For the record, I'm doing this for academic purposes.)
Here's what I have so far:
allDifferent :: (Eq a) => [a] -> Bool
allDifferent list = case list of
[] -> True
(x:xs) -> if x `elem` xs then False else allDifferent xs
What works wonderfully!
Now when I try to do it like this ...
allDifferent2 :: (Eq a) => [a] -> Bool
allDifferent2 list
| null list = True
| (head list) `elem` (tail list) || allDifferent2 (tail list) = False
| otherwise
It just doesn't work as it should. I am getting the following output from GHCi:
*Main> allDifferent2 [1..4]
False
*Main> allDifferent2 [1..5]
True
*Main> allDifferent2 [1..6]
False
*Main> allDifferent2 [1..7]
True
i.e. For every list with an even number of elements, it outputs False and for an odd number of elements, True.
What am I missing? Would anyone like to shine some light?
source to share
Alternative way to use notElem
:
allDifferent :: (Eq a) => [a] -> Bool
allDifferent list = case list of
[] -> True
(x:xs) -> x `notElem` xs && allDifferent xs
Minor option using pattern matching directly in equations:
allDifferent :: (Eq a) => [a] -> Bool
allDifferent [] = True
allDifferent (x:xs) = x `notElem` xs && allDifferent xs
I try to stay away from partial functions like head,tail
so guard based options look worse than me.
source to share
I would do it differently. Recursion + elem
is O (n²). Alternatively, you can sort the list first and then compare the items equally. So sorting is O (n⋅log n) and traversal is O (n). So overall 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)
source to share
Try the following:
allDifferent2::(Eq a) => [a] -> Bool
allDifferent2 list
| list == [] = True
| (head list) `elem` (tail list) = False
| otherwise = allDifferent2(tail list)
If the list is [], you should return True (As @bheklilr said :))
If the list is not null, you can check if the first element is in the tail of the list. If so, return False. Good.
But when you say "if it is in the tail of the list OR allDifferent2 (tail list)" you are killing your function. "If all the items in this list are different, return FALSE " and that's not what you want.
EDIT: Yes it will be @Luis. I fixed that by putting "otherwise" there. When I put guard in front of allDifferent2 (tail list) it checks if this function returned True. So this will work for [1, 1, 2] (my test case), but not for [1, 2, 2] (like your case).
source to share
The simplest sane idiomatic approach I can think of is
allDifferent :: Ord a => [a] -> Bool
allDifferent = pairwiseDifferent . sort
pairwiseDifferent :: Eq a => [a] -> Bool
pairwiseDifferent xs = and $ zipWith (/=) xs (drop 1 xs)
For fun with folds
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)
Another option is to use Set
(some strictness annotations may not be needed):
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
source to share
You can rely on the library functions allDifferent xs = nub xs == xs
.
Or recorded in the non-contact marking: allDifferent = uncurry (==) . (nub &&& id)
.
Using Data.Discrimination.nub this happens in O (n) time.
source to share
Sort the list, group
run equal elements together and check to see if there is exactly one element. all
import Data.List (group, sort)
pairwiseDistinct :: Ord a => [a] -> Bool
pairwiseDistinct xs = all (\ys -> null (tail ys)) (group (sort xs))
Direct version:
pairwiseDistinct = all (null . tail) . group . sort
This assumes that for any two elements x
and y
, x == y
if and only if compare x y == EQ
.
tail
great here because none of the groups will ever be empty, but you can replace drop 1
if you are not partial to the function.
source to share