[Haskell-cafe] Deleting list of elements from Data.Set

[Duncan Coutts]

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