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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe