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
a = [a1, a2, ..., an], you have to find those integers which are repeated at least
ktimes. In case no such element exists you have to print
If there are multiple elements in
awhich are repeated at least
ktimes, 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
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" printList a = putStrLn $ unwords [show i | i <- a]
readNumbers which takes a space separated string and returns a
Num list from that string.
readNumbers :: Show a => Eq a => Num a => Read a => String -> [a] readNumbers = map read . words
run which throws all of this together and runs this
run :: (Show a, Eq a, Num a, Read a) => a -> IO () run 0 = putStr "" run n = do a <- getLine b <- getLine printList $ filt (readNumbers b) (readNumbers a !! 1) run $ n - 1
main the main function. It gets a number
n and then calls
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
count is the limiting factor, but I can't figure out how to optimize them.