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 <pc88m...@gmail.com> wrote: [Chop] > > 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). _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
