On Feb 10, 2008 1:07 PM, Michael Feathers <[EMAIL PROTECTED]> 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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
