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

[Daniel Fischer]

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.