projects
/
haskell-directory.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
[project @ 2005-04-21 09:40:41 by simonmar]
[haskell-directory.git]
/
Data
/
Set.hs
diff --git
a/Data/Set.hs
b/Data/Set.hs
index
7e07fbe
..
eb41f94
100644
(file)
--- a/
Data/Set.hs
+++ b/
Data/Set.hs
@@
-112,7
+112,6
@@
module Data.Set (
) where
import Prelude hiding (filter,foldr,null,map)
) where
import Prelude hiding (filter,foldr,null,map)
-import Data.Monoid
import qualified Data.List as List
import Data.Typeable
import qualified Data.List as List
import Data.Typeable
@@
-208,6
+207,8
@@
singleton x
Insertion, Deletion
--------------------------------------------------------------------}
-- | /O(log n)/. Insert an element in a set.
Insertion, Deletion
--------------------------------------------------------------------}
-- | /O(log n)/. Insert an element in a set.
+-- If the set already contains an element equal to the given value,
+-- it is replaced with the new value.
insert :: Ord a => a -> Set a -> Set a
insert x t
= case t of
insert :: Ord a => a -> Set a -> Set a
insert x t
= case t of
@@
-290,7
+291,9
@@
unions ts
= foldlStrict union empty ts
= foldlStrict union empty ts
--- | /O(n+m)/. The union of two sets. Uses the efficient /hedge-union/ algorithm.
+-- | /O(n+m)/. The union of two sets, preferring the first set when
+-- equal elements are encountered.
+-- The implementation uses the efficient /hedge-union/ algorithm.
-- Hedge-union is more efficient on (bigset `union` smallset).
union :: Ord a => Set a -> Set a -> Set a
union Tip t2 = t2
-- Hedge-union is more efficient on (bigset `union` smallset).
union :: Ord a => Set a -> Set a -> Set a
union Tip t2 = t2
@@
-427,7
+430,7
@@
elems s
{--------------------------------------------------------------------
Lists
--------------------------------------------------------------------}
{--------------------------------------------------------------------
Lists
--------------------------------------------------------------------}
--- | /O(n)/. Convert the set to an ascending list of elements.
+-- | /O(n)/. Convert the set to a list of elements.
toList :: Set a -> [a]
toList s
= toAscList s
toList :: Set a -> [a]
toList s
= toAscList s
@@
-506,15
+509,6
@@
instance Ord a => Ord (Set a) where
compare s1 s2 = compare (toAscList s1) (toAscList s2)
{--------------------------------------------------------------------
compare s1 s2 = compare (toAscList s1) (toAscList s2)
{--------------------------------------------------------------------
- Monoid
---------------------------------------------------------------------}
-
-instance Ord a => Monoid (Set a) where
- mempty = empty
- mappend = union
- mconcat = unions
-
-{--------------------------------------------------------------------
Show
--------------------------------------------------------------------}
instance Show a => Show (Set a) where
Show
--------------------------------------------------------------------}
instance Show a => Show (Set a) where