Jonas Almström Duregård
noneRepeated xs = xs == nub xs
Not quite as bad, nub is O(n^2)
You are correct of course. Still, it will probably be a bit less inefficient if the length of the lists are compared (as opposed to the elements):
noneRepeated xs = length xs == length (nub xs)
[...]
How can you nub in O(n*log n)? Remember, you only have Eq for nub.
Again note that the big advantage of my method is laziness. The comparison will end on the first duplicate found. Using the following nub implementation the overall time complexity should be O(n * log n), but may be space-intensive, because it uses O(n) space. Also note that it has a different context (the type needs to be Ord instead of Eq): import qualified Data.Set as S import Data.List myNub :: Ord a => [a] -> [a] myNub = concat . snd . mapAccumL nubMap S.empty where nubMap s x | S.member x s = (s, []) | otherwise = (S.insert x s, [x]) Greets Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://blog.ertes.de/