1
\$\begingroup\$

I have two functions. Both have to have unique elements, one with Integers and the other a String which returns a list of Char. My runtime is currently quite high and I'm not allowed to use imports, but I was wondering how to improve them:

uniqueInt:: [Int] -> [Int]
uniqueInt[] = []
uniqueInt xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Example: uniqueInt [1,2,1,3,1,2] = [1,2,3]

uniqueString :: String -> [Char]
uniqueString ""=[]
uniqueString xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Example: uniqueString "hello"="helo"

\$\endgroup\$
1
\$\begingroup\$

Firstly you might want to make use of a Haskell feature to combine both functions into one:

unique :: Eq a => [a] -> [a]
unique [] = []
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

Now let's talk about performance. Obviously lists aren't great in this respect, since take is quite expensive and needs to iterate through the list, as well as notElem, which will, again iterate through the list. Plus this is also constructing new lists, which leads to GC, which leads to decreased performance.

So best option would be to go through the list only once, putting each element into a set while it's then only collecting the elements which haven't been in the set yet at that moment.

That's of course a very imperative way of doing it. And regardless, if you're not allowed to use imports you'd have to create the respective data structures yourself, which I'd say isn't worth the effort.


In any case, at least within the constraints set it's still possible to make this a bit more efficient, basically by copying nub's implementation:

unique :: Eq a => [a] -> [a]
unique l = unique' l []
  where
    unique' [] _ = []
    unique' (x:xs) ls
           | x `elem` xs = unique' xs ls
           | otherwise   = x : unique' xs (x:ls)
\$\endgroup\$
2
  • \$\begingroup\$ I can't change the signature, any advice how to combine? \$\endgroup\$ – Yuki1112 Apr 10 at 14:59
  • \$\begingroup\$ If you can't change the signature you've to copy it and keep using [Int] respectively String instead of a of course (String is an alias for [Char] btw., either use String or [Char], not both). Plus you'd remove the Eq a => part of course. \$\endgroup\$ – ferada Apr 10 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.