CODEWITHSUNDEEP
listhaskellfunctional-programmingunique
user12117801
user12117801

Reputation:

How to take only unique elements from a list?

I have a list, say [1,2,3,4,3,2,4]. I would like to output every element once, for example [1,2,3,4]. How can I do this in Haskell?

Upvotes: 4

Views: 2933

Answers (4)

Redu
Redu

Reputation: 26191

Basically since sorting in Haskell lists are quite fast (best case O(n) worst case O(nlogn) we might use sorting first and then folding for an efficient solution with an additional effect of getting a sorted result, if that would be beneficial.

The following code is for minimal cons operations;

Prelude Data.List
λ> :{
λ| foldr (\e rs -> case rs of
λ|                 []     -> [e]
λ|                 (x:xs) -> if x == e then rs else e:rs) [] $ sort [8,8,4,3,2,3,3,2,1,8,3,5]
λ| :}
[1,2,3,4,5,8]

and the following is, as per pointed out by @Joseph Sible-Reinstate Monica for enhanced laziness.

Prelude Data.List
λ> :{
λ| foldr (\e rs -> e : case rs of
λ|                 []     -> []
λ|                 (x:xs) -> if x == e then xs else rs) [] $ sort [8,8,4,3,2,3,3,2,1,8,3,5]
λ| :}
[1,2,3,4,5,8]

Upvotes: 2

Levkovich Efrat
Levkovich Efrat

Reputation: 111

You can do it with sets using Data.set:

import qualified Data.Set as Set
lst = [1,2,3,4,1,2,3]
y =  Set.fromList lst

The output is:

y
=> fromList [1,2,3,4]

Upvotes: 11

Yuri Kovalenko
Yuri Kovalenko

Reputation: 1375

There is a nub function exactly for that. However, it has complexity of O(n^2), which is not so good. In case of numbers (or any Ord type) you can make your own unique function like this:

unique :: Ord a => [a] -> [a]
unique = map head . group . sort

You'll need to import Data.List. It acts like this:

sort [1,2,3,1,2] -> [1,1,2,2,3]        -- to order the elements
group [1,1,2,2,3] -> [[1,1],[2,2],[3]] -- to group equal ones
map head [[1,1],[2,2],[3]] -> [1,2,3]  -- to take first of groups

That has complexity of O(n log n), which is a way better.

Upvotes: 5

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477210

You can make use of nub :: Eq a => [a] -> [a] which acts as a uniqness filter. It will however require O(n2) since it does not use a data structure like a hashset.

For example:

Prelude Data.List> nub [1,2,3,4,3,2,4]
[1,2,3,4]

If the elements are of a type that is a member of the Hashable typeclass, you can use for example hashNub :: (Eq a, Hashable a) => [a] -> [a] to perform a uniqness filter in O(n log n):

Prelude ClassyPrelude> hashNub [1,2,3,4,3,2,4]
[1,2,3,4]

Upvotes: 11

Related Questions