Re: [Haskell-cafe] nub vs. find + (:) Is this abysmal code?
2008/2/10, Michael Feathers [EMAIL PROTECTED]: 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ï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nub vs. find + (:) Is this abysmal code?
On Feb 10, 2008 1:14 PM, Chaddaï Fouché [EMAIL PROTECTED] wrote: This is much better, though probably better writed : addProduct :: [Product] - Product - [Product] addProduct inventory p | elem p inventory = p : inventory | otherwise = inventory Maybe addProduct :: [Product] - Product - [Product] addProduct inventory p = p : delete p inventory and probably even better with a Set instead of a List... import qualified Data.Set as S addProduct :: S.Set Product - Product - S.Set Product addProduct = flip S.insert -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nub vs. find + (:) Is this abysmal code?
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
[Haskell-cafe] nub vs. find + (:) Is this abysmal code?
How bad is this: addProduct :: [Product] - Product - [Product] addProduct inventory product = nub (product : inventory) compared to this: addProduct :: [Product] - Product - [Product] addProduct inventory p | isNothing (find (==p) inventory)= p : inventory | otherwise= inventory 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. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nub vs. find + (:) Is this abysmal code?
On Feb 10, 2008 1:20 PM, Felipe Lessa [EMAIL PROTECTED] wrote: Maybe addProduct :: [Product] - Product - [Product] addProduct inventory p = p : delete p inventory Oh, forget this, it will keep rewriting the tail of the list, which is a Bad Thing (TM). -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
