Re: [Haskell-cafe] Deleting list of elements from Data.Set
On Wed, 2008-01-30 at 11:05 +, Gracjan Polak wrote: > > My strictness analyser in my brain hurts. Which one (foldl,foldl',foldr) is > the > best way? > > Prelude Data.Set Data.List> let s = fromList [1,2,3,4,5] > Loading package array-0.1.0.0 ... linking ... done. > Loading package containers-0.1.0.0 ... linking ... done. > > Prelude Data.Set Data.List> foldl (.) id > (Data.List.map Data.Set.delete [1,3,5]) s > fromList [2,4] > > Prelude Data.Set Data.List> foldl' (.) id > (Data.List.map Data.Set.delete [1,3,5]) s > fromList [2,4] > > Prelude Data.Set Data.List> foldr (.) id > (Data.List.map Data.Set.delete [1,3,5]) s > fromList [2,4] > > Which one is best? Or how about: Data.List.foldr (Data.Set.delete) s [1,3,5] or Data.List.foldl' (flip Data.Set.delete) s [1,3,5] if delete is strict in the set then I'd pick the foldl' otherwise the foldr. It's possible to implement sets either way but I happen to know that Data.Set is strict in its tree structure. These are always going to be O(m * log n) for deleting m elements from a set of size n. If you're deleting a lot of elements then there's also s `Data.Set.difference` Data.Set.fromList [1,3,5] which is O (n + m * log m) rather than O(m * log n) or if the elements you're deleting are already sorted you can shave off the log m using Data.Set.fromAscList to get just O (n + m). Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Deleting list of elements from Data.Set
On Jan 30, 2008 11:05 AM, Gracjan Polak <[EMAIL PROTECTED]> wrote: > My strictness analyser in my brain hurts. Which one (foldl,foldl',foldr) is > the > best way? > > Prelude Data.Set Data.List> let s = fromList [1,2,3,4,5] > Loading package array-0.1.0.0 ... linking ... done. > Loading package containers-0.1.0.0 ... linking ... done. > > Prelude Data.Set Data.List> foldl (.) id > (Data.List.map Data.Set.delete [1,3,5]) s > fromList [2,4] > > Prelude Data.Set Data.List> foldl' (.) id > (Data.List.map Data.Set.delete [1,3,5]) s > fromList [2,4] I think this one. Map and Set are strict in their keys, so using foldl' won't lose you any generality and will be stricter (so hopefully faster). My internal heuristic is this: foldr when you can get some of the information without computing the whole result, foldl' when you can't, and never use foldl. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Deleting list of elements from Data.Set
My strictness analyser in my brain hurts. Which one (foldl,foldl',foldr) is the best way? Prelude Data.Set Data.List> let s = fromList [1,2,3,4,5] Loading package array-0.1.0.0 ... linking ... done. Loading package containers-0.1.0.0 ... linking ... done. Prelude Data.Set Data.List> foldl (.) id (Data.List.map Data.Set.delete [1,3,5]) s fromList [2,4] Prelude Data.Set Data.List> foldl' (.) id (Data.List.map Data.Set.delete [1,3,5]) s fromList [2,4] Prelude Data.Set Data.List> foldr (.) id (Data.List.map Data.Set.delete [1,3,5]) s fromList [2,4] Which one is best? -- Gracjan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
