# Filter Duplicate Elements in Haskell

I'm working on HackerRank to try to improve my Haskell skills along side with reading Haskell Programming from first principles. I wrote a program that works, but it seems to time out on large input sets. The purpose of the program is

Given a list of n integers a = [a1, a2, ..., an], you have to find those integers which are repeated at least k times. In case no such element exists you have to print -1.

If there are multiple elements in a which are repeated at least k times, then print these elements ordered by their first occurrence in the list.

So I wrote a few different functions to help with this.

### count which counts the number of occurrences of an element in a list

count :: Eq a => Integral b => a -> [a] -> b
count e [] = 0
count e (a:xs) = (count e xs +) $if a == e then 1 else 0  ### uniq which removes duplicates from a list uniq :: Eq a => [a] -> [a] -> [a] uniq x [] = x uniq [] (a:xs) = uniq [a] xs uniq x (a:xs) = if a elem x then uniq x xs else uniq (a:x) xs  ### filt which filters through a list and removes elements that don't occur at least k times. filt :: Show a => Num a => Read a => Eq a => Integral b => [a] -> b -> [a] filt a b = reverse$ uniq [] [i | i <- a, count i a >= b]


### printList which prints a list as a space separated list or prints -1 if the list is empty.

printList :: Show a => [a] -> IO ()
printList [] = putStrLn "-1"
run $n - 1  ### main the main function. It gets a number n and then calls run n. main :: IO () main = do a <- getLine run$ read a


This code works, for example, with the input

3
9 2
4 5 2 5 4 3 1 3 4
9 4
4 5 2 5 4 3 1 3 4
10 2
5 4 3 2 1 1 2 3 4 5


and gives the desired output of

4 5 3
-1
5 4 3 2 1


However, with larger datasets this code is incredibly slow. I'm guessing it's because the recursion is less than optimal, but I can't really pinpoint what is taking so long. My best guess is that uniq or count is the limiting factor, but I can't figure out how to optimize them.

• The primary problem is uniq, count, and filt are all O(n). Take a look at hackage.haskell.org/package/containers and see if there is a data structure that would work better. Dec 21, 2016 at 21:13

If you write uniq as a right fold, you don't need to pass an accumulator through, and the list comes out in the right order:

uniq :: Eq a => [a] -> [a]
uniq [] = []
uniq (x:xs) = (if x elem xs then id else (x:)) $uniq xs filt :: Show a => Num a => Read a => Eq a => Integral b => [a] -> b -> [a] filt k is = uniq [i | i <- is, count i is >= k]  (Edit: Actually that one throws out the first of each two equal elements, not the last. Heres one without that problem: uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/=x) xs)  ) You've commendably already brought count into a form that allows it to be written in terms of library combinators: count :: Eq a => Integral b => a -> [a] -> b count e = sum . map (\a -> if a == e then 1 else 0)  That's a bit ugly due to lambdas though, here's a nicer version: count e = length . filter (== e)  For separation of monadic and pure code (and generally for factoring out common code from across cases), here's a showList to replace printList: showList :: Show a => [a] -> String showList [] = "-1" showList a = unwords [show i | i <- a]  Calling a monadic action a given number of times doesn't need manual recursion, and thus also doesn't need to give the repeated action a name: main :: IO () main = do a <- readLn replicateM_ a$ do
[_n, k] <- map read . words <$> getLine numbers <- map read . words <$> getLine
putStrLn $showList$ filt k numbers


(I think readNumbers doesn't deserve a name.)

In case the order in which the output is given isn't important, here's a version that doesn't require quadratic time because each element is compared to every other:

filt k = map head . filter ((>=k) . length) . group . sort


which relies on Data.Lists sort` being faster than quadratic time.

• You are some type of Haskell wizard here. This is an absolutely beautiful piece of code. Dec 22, 2016 at 22:44