[Haskell-cafe] using mutable data structures in pure functions

[Stephen Tetley]

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 <pc88mxer at 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).