Re: [Haskell-cafe] nub vs. find + (:) Is this abysmal code?
On Sun, 10 Feb 2008, Michael Feathers wrote: > 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 Data.Set is first choice, 'elem' is second choice, but still better than 'isNothing (find ...)'. ___ 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
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?
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: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
