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

[Felipe Lessa]

On Feb 10, 2008 1:07 PM, Michael Feathers <mfeathers at mindspring.com> wrote:
> How bad is this:
>
> addProduct :: [Product] -> Product -> [Product]
> addProduct inventory product = nub (product : inventory)
>

O(n²) as is nub.

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

O(n) as is find.

> My guess is that the latter is more efficient, but then when I think
> about laziness, I wonder whether the first is a fair trade.

I don't think so =). Still, you should be using Data.Set which will
take you to O(log n).

-- 
Felipe.