CODEWITHSUNDEEP
listfunctionhaskellelementghci
James Johnson
James Johnson

Reputation: 121

How to remove a duplicated element in a function with a list?

I'm a newbie when it comes to Haskell and I'm confused with a few things. I'm trying to remove duplicated elements in this functions list:

qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = 
     qsort smaller ++ [x] ++ qsort larger
     where 
          smaller = [a | a <- xs, a <= x] 
          larger = [b | b <- xs, b > x]

I attempted to do this by importing Data.List and using the nub [] function:

qsort :: [Int] -> [Int]
qsort [] = nub[]

But, if I do qsort [2, 6, 3, 3], it still returns with [2, 3, 3, 6].

Am I using the nub function wrong or is there something else I am missing?

Thank you

Upvotes: 2

Views: 86

Answers (3)

St&#233;phane Laurent
St&#233;phane Laurent

Reputation: 84619

See the unique function in the (Unique)[https://hackage.haskell.org/package/Unique-0.4.7.2/docs/Data-List-Unique.html] package.

unique [2,3,6,6,3]
[2,3,6]

Upvotes: 0

RoadRunner
RoadRunner

Reputation: 26325

As pointed out in @Chad Gilbert's answer, you need to apply nub on the final sorted list. Unfortunately this function is O(n^2), and would be pretty innefficient if the list gets long.

You can improve the overall complexity to O(nlogn)(cost of sorting), if you group identical elements together and just take the first item, which is just an O(n) operation. You can accomplish this with the map, group and head functions.

With these suggestions, here is another way of writing your function:

import Data.List

qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (pivot:others) = map head $ group $ qsort lowers ++ [pivot] ++ qsort highers
    where lowers = filter (<pivot) others
          highers = filter (>=pivot) others

Which works as follows:

*Main> qsort [2, 6, 3, 3]
[2,3,6]

Upvotes: 1

Chad Gilbert
Chad Gilbert

Reputation: 36385

Your example shows you only using nub on the empty list (nub []), which doesn't actually do anything. You have to apply it to the result of the main body of qsort:

qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = 
     nub $ qsort smaller ++ [x] ++ qsort larger
     where 
          smaller = [a | a <- xs, a <= x] 
          larger = [b | b <- xs, b > x]

This, however, is unnecessarily expensive because it runs nub on every branch of the function. Further optimization is left to you.

Upvotes: 1

Related Questions