[Haskell-cafe] Time consumption nub

[Mirko Rahn]

Arie Groeneveld wrote:

> Ok, so when do I use nub instead of 'map head.group.sort'?

Never. If |nub_sort=map head.group.sort| is applicable, then you are 
dealing with a member of class Ord, so use the O(n*log n) |nub_sort|. If 
you want to preserve the relative order of the input list, use something 
like

nub_cache :: Ord a => [a] -> [a]
nub_cache = onub Set.empty
     where onub seen (x:xs)
	      | Set.member x seen =     onub               seen  xs
	      | otherwise         = x : onub (Set.insert x seen) xs
	  onub _ _ = []

|nub_cache| also works for infinite lists, btw.

/BR

-- 
-- Mirko Rahn -- Tel +49-721 608 7504 --
--- http://liinwww.ira.uka.de/~rahn/ ---