[Haskell-cafe] function unique

[Jonathan Cast]

On Thursday 12 July 2007, Dan Weston wrote:
> Now that I mention it, the base case is much less often called than the
> recursive case, so I would in hindsight flip the order of the two
> (mutually exclusive) partial function definitions:
>
> unique :: Eq a => [a] -> [a]
> unique (x:xs) = x : (unique . filter (/= x) $ xs)
> unique []     = []
>
> This should be marginally more efficient. I doubt that GHC would
> automatically detect that a) they are mutually exclusive and b) the
> second is called less often than the first!

Actually, it would (well, sort of).  GHC expends a good deal of effort looking 
for cases where pattern-matching is mutually-exclusive, and flattens it out 
to

unique xn' = case xn' of
  [] -> []
  x : xn -> x : unique (filter (/= x) xn)

where each branch is equally efficient.

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs