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