[Haskell-cafe] function unique

[Tim Chevalier]

On 7/12/07, Dan Weston <westondan at imageworks.com> 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!

Of course GHC detects that the cases are mutually exclusive. The code
above desugars into a single definition of unique with a case
expression on its argument. In Core, case expressions have at most one
alternative for each data constructor of the type of the scrutinee,
and since each alternative corresponds to a different top-level data
constructor, alternatives are mutually exclusive. As for point (b), it
hardly matters, since GHC will rearrange case alternatives at will
(and I don't think the order of alternatives has any operational
meaning anyway.)

If you want to see this for yourself, try running GHC with the
-ddump-simpl flag on a simple example (like the one above).

Cheers,
Tim

-- 
Tim Chevalier* catamorphism.org *Often in error, never in doubt
"What doesn't kill you, makes you stronger -- or puts you on a talk
show."  --Carrie Fisher