Haskell - Checking if all list elements are unique

haskell remove duplicates from list
haskell nub
haskell index of element in list
erlang remove duplicates from list
prolog unique
ocaml remove duplicates from list
haskell list of lists
fortran remove duplicates in array

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?

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.

unique elements in a haskell list, The nub function from Data.List (no, it's actually not in the Prelude) definitely does something like what you want, but it is not quite the same as  I need to compare if all elements of a given list are unique. (For the record I am doing so for academic purposes.) Sign up or log in to customize your list. more

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)

Data.List.Unique, the first - all elements with removed duplicates (like sortUniq but the result is isUnique function is to check whether the given element is unique in the list or not​. The problem is you are trying to insert as the first element of the list, list5 which is incorrect. You have to access the first element of the list and insert it to that list. This can be done using the following code >>> list5 = [[], [(1,2,3,4), 2, 5]]

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).

Data/List/Unique.hs, repeatedBy (>2) "This is the test line" == " eist" repeatedBy :: Ord a => (Int '​allUnique' checks whether all elements of the list are unique -- -- > allUnique "foo​  isUnique function is to check whether the given element is unique in the list or not. It returns Nothing when the element does not present in the list.

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

Data.List.UniqueStrict, Safe Haskell, Safe Library provides functions to find unique and duplicate elements in the list. isUnique function is to check whether the given element is unique in the list or allUnique checks whether all elements of the list are unique The original list is : [1, 3, 4, 6, 7] List contains all unique elements Method #3 : Using Counter.itervalues() This is one of the different methods and uses the frequency obtained of all the elements using Counter, and checks if any of the frequency is greater than 1.

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.

Data.List.UniqueUnsorted, isUnique function is to check whether the given element is unique in the list or not​. It returns allUnique checks whether all elements of the list are unique Haskell has a function called filter which will do this for you. Beware though: it should really be named 'select' instead. For example, filter odd xs returns a list of odd numbers. That is, it deletes everything that is not odd.

[Haskell-beginners] Unique integers in a list, and use it like this:: > > unique (x:xs) = if not(isin x xs) then [x] ++ unique(xs) else It also needs the empty list check to terminate. x <- (x:xs), not(isin x xs)] ++ unique xs > The not(isin x xs) will definitely fail for all the elements  The isSubsequenceOf function takes two lists and returns True if all the elements of the first list occur, in order, in the second. The elements do not have to occur consecutively. isSubsequenceOf x y is equivalent to elem x (subsequences y). Examples Expand

Determining whether a list contains duplicates - haskell, I have a list of Ord a, and would like to "efficiently" determine whether or not it contains List.Unique module on Hackage, but it just does the second solution, in a duplicates hasDuplicatesWith seen (x:xs) = -- If we have seen the current item useful is to run it on another thread, but then it may just devour all the memory. Producing all possible combinations of a list. Haskell function to explode a list. 5. Unique elements of a list and corresponding indices in Haskell.

Check if list contains a value, in Haskell, For empty list false. If first element match true. Check rest of the elements recursively. Ada; C; Caml; Clojure; Clojure; C++; C++; C#; D; Dart; Elixir; Elixir; Erlang  It returns triple:---- * the first - all elements with removed duplicates (like 'sortUniq' but the result is not sorted)---- * the second - the elements that are repeated at least once in the list (result is the same as 'repeated' but not sorted)---- * the third - the unique elements that do not have duplicates (result is the same as 'unique

Comments
  • Shouldn't it be null list = True to match your original implementation?
  • Yes sorry .. typo.. just fixed that, the bug however, persists.
  • So you have head list `elem` tail list || allDifferent2 (tail list) = False, which is basically saying "if the first element is somewhere in the list, or if all the rest of the list is full of uniques then return False". Are you sure that's the behavior you want? You might be able to make it simpler with head list `elem` tail list = allDifferent2 (tail list), I think that'll work better for you.
  • If your recursive call to allDifferent2 returns True then the guard passes and you then return False which may not be what you want.
  • Interesting, what harm is there in using partial functions?
  • @LuisDosReis If you ever ask for head [] or tail [], the whole program aborts (crashes). This does not happen with (exhaustive) pattern matching. (And -Wall helps in detecting non exhaustiveness).
  • @LuisDosReis In a guard solution, remember you have to add an | otherwise = blah case
  • @LuisDosReis If your code ends with a list of guards, the last must be equivalent to otherwise, since it has to catch all the remaining cases. You may use a more complex check, but there's no real reason to do so.
  • @LuisDosReis It's much easier to work with total functions. In fact you can derive theorems from the type of a total function and be sure that it has some property simply looking at the type. If the function is partial this kind of things gets harder, because the function could blow up at any time and you generally cannot easily derive properties as easily. This makes both reasoning and proving correctness much more difficult.
  • I'd suggest comparePairwise (x:xs@(y:_)) = x /= y && comparePairwise xs ; comparePairwise _ = True