[Haskell-cafe] nub vs. find + (:) Is this abysmal code?

[Chaddaï Fouché]

2008/2/10, Michael Feathers <mfeathers at mindspring.com>:
>
> How bad is this:
>
> addProduct :: [Product] -> Product -> [Product]
> addProduct inventory product = nub (product : inventory)
>

This is pretty terrible, if the list is consumed afterward (which we
assume it will be) we should have something like a O(n^3)
complexity... Since nub is O(n^2).

>
> compared to this:
>
> addProduct :: [Product] -> Product -> [Product]
> addProduct inventory p
>     | isNothing (find (==p) inventory)    = p : inventory
>     | otherwise                                        = inventory
>

This is much better, though probably better writed :
> addProduct :: [Product] -> Product -> [Product]
> addProduct inventory p
>     | elem p inventory = p : inventory
>     | otherwise           = inventory

and probably even better with a Set instead of a List...

-- 
Jedaï