There is a "trick" to `nub` where you couldn't implement the internal
lookup list with an (assumed faster) search tree anyway.
`nub` only mandates equality not ordering, so building a ordered
structure like a binary tree is impossible. In practice i would be
hard to beat list as the intermediate structure in this case.
On 12 March 2012 03:38, E R
For example, consider the definition of Data.List.nub:
nub l = nub' l [] where nub' [] _ = [] nub' (x:xs) ls | x `elem` ls = nub' xs ls | otherwise = x : nub' xs (x:ls)
Clearly the memory allocated to ls never escapes nub', so it seems that ls could be replaced with a mutable data structure (with an eye towards improving performance in special cases).