Re: [Haskell-beginners] Eq a => [a]->[a]

3 Dec 2009


      Am Donnerstag 03 Dezember 2009 20:00:00 schrieb Daniel Fischer:
...
You can remove one factor (log k) by checking the size instead of
membership:
f xs = map fst . takeWhile snd . zip xs . zipWith ((. S.size) . (==)) [1 ..
] $ cums where
      cums = tail $ scanl (flip S.insert) S.empty xs
I think for *short* nubbed prefixes, Brent's version is faster, but I've no
idea yet when short stops (10, 100, 1000?).
Couldn't measure a difference for short lists, starts to become faster than Brent's 
between 10^5 and 10^6. The manual loop

f :: Ord a => [a] -> [a]
f xs = go 1 S.empty xs
      where
        go i s (y:ys)
          | i == S.size s'  = y:go (i+1) s' ys
          | otherwise       = []
            where
              s' = S.insert y s
        go _ _ _ = []

is ~15% faster.