[Haskell-cafe] Re: Function to detect duplicates
Ertugrul Soeylemez
es at ertes.de
Wed Feb 24 08:25:20 EST 2010
Jonas Almström Duregård <jonas.duregard at gmail.com> wrote:
> >>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/
More information about the Haskell-Cafe
mailing list