[Haskell-cafe] Deleting list of elements from Data.Set
Duncan Coutts
duncan.coutts at worc.ox.ac.uk
Wed Jan 30 06:23:52 EST 2008
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
More information about the Haskell-Cafe
mailing list