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

On Feb 10, 2008 1:07 PM, Michael Feathers 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.