Fri Oct 7 10:52:15 WEST 2005 Malcolm.Wallace@cs.york.ac.uk
* expand the API
Bring the exports closer to those currently in package base, namely
change "single" to "singleton", and add "map" and "mapMonotonic".
{
hunk ./lib/DData/Set.hs 23
- > ... Set.single "Paris" [_$_]
+ > ... Set.singleton "Paris" [_$_]
hunk ./lib/DData/Set.hs 29
- > ... S.single "Berlin" [_$_]
+ > ... S.singleton "Berlin" [_$_]
hunk ./lib/DData/Set.hs 82
- , single
+ , singleton
hunk ./lib/DData/Set.hs 98
+ , Set.map
+ , mapMonotonic
hunk ./lib/DData/Set.hs 128
-import Prelude hiding (filter)
+import Prelude hiding (filter,map)
+import List (map)
hunk ./lib/DData/Set.hs 196
-single :: a -> Set a
-single x [_$_]
+singleton :: a -> Set a
+singleton x [_$_]
hunk ./lib/DData/Set.hs 207
- Tip -> single x
+ Tip -> singleton x
hunk ./lib/DData/Set.hs 367
+{----------------------------------------------------------------------
+ Map
+----------------------------------------------------------------------}
+
+-- | /O(n*log n)/. [_$_]
+-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
+-- [_$_]
+-- It's worth noting that the size of the result may be smaller if,
+-- for some @(x,y)@, @x \/= y && f x == f y@
+
+map :: (Ord a, Ord b) => (a->b) -> Set a -> Set b
+map f = fromList . List.map f . toList
+
+-- | /O(n)/. The [_$_]
+--
+-- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is monotonic.
+-- /The precondition is not checked./
+-- Semi-formally, we have:
+-- [_$_]
+-- > and [x < y ==> f x < f y | x <- ls, y <- ls] [_$_]
+-- > ==> mapMonotonic f s == map f s
+-- > where ls = toList s
+
+mapMonotonic :: (a->b) -> Set a -> Set b
+mapMonotonic f Tip = Tip
+mapMonotonic f (Bin sz x l r) =
+ Bin sz (f x) (mapMonotonic f l) (mapMonotonic f r)
+
hunk ./lib/DData/Set.hs 472
- -> c (bin x4 (bin x2 (single x1) (single x3)) (single x5)) xx
+ -> c (bin x4 (bin x2 (singleton x1) (singleton x3)) (singleton x5)) xx
hunk ./lib/DData/Set.hs 643
- Tip -> single x
+ Tip -> singleton x
hunk ./lib/DData/Set.hs 649
- Tip -> single x
+ Tip -> singleton x
hunk ./lib/DData/Set.hs 989
- = (insert x empty == single x)
+ = (insert x empty == singleton x)
hunk ./lib/DData/Set.hs 1031
- = union t (single x) == insert x t
+ = union t (singleton x) == insert x t
}