CODEWITHSUNDEEP
listhaskellfunctional-programmingcomparison
Luis Dos Reis
Luis Dos Reis

Reputation: 393

Haskell - Checking if all list elements are unique

I need to compare if all elements of a given list are unique. (For the record I am doing so for academic purposes.)

Here is what I have thus far:

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

Which 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 intended. I get 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 amount of elements it outputs False and for an odd amount of elements, True.

What am I missing? Would anyone care to shine some light?

Upvotes: 5

Views: 10633

Answers (7)

Gonçalo Faria
Gonçalo Faria

Reputation: 9

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,([],[])))

As you can see the structure of this solution is very similar to quickSort. It shares as an intermediate data structure a binary tree and for that reason, the time complexity is extremely similar.

Upvotes: 0

gdejohn
gdejohn

Reputation: 7579

Sort the list, group runs of equal elements together, and check if all groups have exactly one element.

import Data.List (group, sort)

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

Point-free 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 is fine here because none of the groups will ever be empty, but you can substitute drop 1 if you're averse to partial functions.

Upvotes: 1

sshine
sshine

Reputation: 16105

You can rely on library functions: allDifferent xs = nub xs == xs.

Or, written in point-free notation: allDifferent = uncurry (==) . (nub &&& id).

Using Data.Discrimination.nub, this happens in O(n) time.

Upvotes: 3

dfeuer
dfeuer

Reputation: 48580

The simplest reasonable 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 a Set (some of the strictness annotations may not actually be necessary):

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

Upvotes: 2

Eugene Sh.
Eugene Sh.

Reputation: 18299

I would do this differently. Recursion + elem is O(n²). Alternatively you can first sort the list, and then compare elements pairwise. This way the sorting is O(n⋅log n), and the traversal 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)

Upvotes: 5

Xaphanius
Xaphanius

Reputation: 619

Try this:

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 isn't null, you can verify if the first element is in the tail of the list. If it is, return False. Okay.

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 elements are different in this list, return FALSE", and that isn't what you want.

EDIT: Yeah, it will @Luis. I fixed that by putting that "otherwise" there. When I put the guard before the allDifferent2(tail list) it checked if this function returned True. Thus it would work for [1, 1, 2] (my test-case) but not for [1, 2, 2] (similar to your case).

Upvotes: 1

chi
chi

Reputation: 116139

An alternative exploiting notElem:

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

Minor variant, using pattern matching directly in the equations:

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

I tend to stay away from partial functions like head,tail, so the variants based on guards look worse to me.

Upvotes: 9

Related Questions