Dear GHC developers, How do you think, maybe, Data.Set also needs to provide `lookup' ? For example, I have data D = D Int String, with the instances Eq and Ord defined by the first coordinate. I do use Map Int String, and for a certain reason, also use Set D. Then, for example, the function check :: D -> Set D -> Bool check (D i name) s = case Set.lookup (D i name) s of Just (D _ nm) -> name == nm _ -> False looks natural, apart that there is no Set.lookup. ----------------- Serge Mechveliani mechvel@botik.ru
Serge D. Mechveliani wrote:
How do you think, maybe, Data.Set also needs to provide `lookup' ?
Admittingly, using 'Set.filter (==e) s' to find the matching element may be a bit slower. When trying to use 'Set.intersection s $ singleton e' I just noticed that intersection is not left-biased (see below)! I'm not sure if Data.Set should be extended to better support elements with an equivalence relation and a corresponding order. I've such sets too, but never really cared about the additional component. Do you also want functions 'insertWith', 'unionWith', 'splitLookup' (and what not)? I'ld rather suggest to use Data.Map instead and use a proper total order for the keys (although that may also be awkward). Christian *Main> findMin $ union (singleton $ D 0 "3") $ singleton $ D 0 "2" D 0 "3" *Main> findMin $ intersection (singleton $ D 0 "3") $ singleton $ D 0 "2" D 0 "2"
Christian Maeder wrote:
When trying to use 'Set.intersection s $ singleton e' I just noticed that intersection is not left-biased (see below)!
Set.intersection is neither left- nor right-biased but biased towards the smaller set. I think that needs to be changed (and that may require a function splitLookup). At least the documentation should be adjusted as long as the properties for such pseudo-sets do not correspond to those of maps. Christian
Christian Maeder wrote:
Set.intersection is neither left- nor right-biased but biased towards the smaller set. I think that needs to be changed (and that may require a function splitLookup).
Below is my code proposal. I'm not sure if splitLookup should be exported. And I'm not sure if splitMember should remain as it is (more efficient?) or should be reimplemented using splitLookup (better reuse). The new intersection function is left-biased and traverses the smaller tree also in every recursive call (but I'm not sure if that's better). The comment "Intersection is more efficient on (bigset `intersection` smallset)" needs to be deleted anyway as it is already wrong for the current version. Christian -- | /O(n+m)/. The intersection of two sets. intersection :: Ord a => Set a -> Set a -> Set a intersection Tip t = Tip intersection t Tip = Tip intersection t1@(Bin s1 x1 l1 r1) t2@(Bin s2 x2 l2 r2) = if s1 >= s2 then let (lt,found,gt) = splitLookup x2 t1 tl = intersection lt l2 tr = intersection gt r2 in case found of Just x -> join x tl tr Nothing -> merge tl tr else let (lt,found,gt) = splitMember x1 t2 tl = intersection l1 lt tr = intersection r1 gt in if found then join x1 tl tr else merge tl tr splitMember :: Ord a => a -> Set a -> (Set a,Bool,Set a) splitMember x t = let (l,m,r) = splitLookup x t in (l,maybe False (const True) m,r) -- | /O(log n)/. Performs a 'split' but also returns the pivot -- element that was found in the original set. splitLookup :: Ord a => a -> Set a -> (Set a,Maybe a,Set a) splitLookup x Tip = (Tip,Nothing,Tip) splitLookup x (Bin sy y l r) = case compare x y of LT -> let (lt,found,gt) = splitLookup x l in (lt,found,join y gt r) GT -> let (lt,found,gt) = splitLookup x r in (join y l lt,found,gt) EQ -> (l,Just y,r)
On Thu, Sep 15, 2005 at 02:40:25PM +0200, Christian Maeder wrote:
Serge D. Mechveliani wrote:
How do you think, maybe, Data.Set also needs to provide `lookup' ?
Admittingly, using 'Set.filter (==e) s' to find the matching element may be a bit slower.
When trying to use 'Set.intersection s $ singleton e' I just noticed that intersection is not left-biased (see below)!
I'm not sure if Data.Set should be extended to better support elements with an equivalence relation and a corresponding order. I've such sets too, but never really cared about the additional component.
Do you also want functions 'insertWith', 'unionWith', 'splitLookup' (and what not)?
I'ld rather suggest to use Data.Map instead and use a proper total order for the keys (although that may also be awkward).
Thank you for the help. Set.filter (==e) s looks like similar to find (== e) . Set.toList s, which is slow. Set.intersection s $ singleton e has a chance to be near as fast as `member'. But to have `lookup' looks most natural, to my mind. Generally: I do not know. I would rely on the opinion of developers. If they decide anything about this, then all right. ----------------- Serge Mechveliani mechvel@botik.ru
participants (2)
-
Christian Maeder -
Serge D. Mechveliani