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
On Jan 30, 2008 11:05 AM, Gracjan Polak
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
On Wed, 2008-01-30 at 11:05 +0000, 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
Duncan Coutts
Data.List.foldr (Data.Set.delete) s [1,3,5] or Data.List.foldl' (flip Data.Set.delete) s [1,3,5]
There will be a day when I finally grasp foldr/foldl :)
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).
Thanks for advice. My data is sorted so the above applies really well. -- Gracjan
Gracjan Polak wrote:
Data.List.foldr (Data.Set.delete) s [1,3,5] or Data.List.foldl' (flip Data.Set.delete) s [1,3,5]
There will be a day when I finally grasp foldr/foldl :)
Maybe http://en.wikibooks.org/wiki/Haskell/Performance_Introduction http://www.haskell.org/haskellwiki/Stack_overflow helps to make that day dawn earlier :) Note that in your original approach of fold (.) id , it doesn't really matter whether you use foldr or foldl' (except for argument order!) because the latter would only evaluate to a function Data.Set -> Data.Set which is not very useful. In contrast, Duncan's code evaluates to Data.Set , that's what you want to be strict in. Regards, apfelmus
participants (4)
-
apfelmus -
Duncan Coutts -
Gracjan Polak -
Luke Palmer