Rename join to link ...
authorMilan Straka <fox@ucw.cz>
Mon, 7 Oct 2013 13:15:59 +0000 (15:15 +0200)
committerMilan Straka <fox@ucw.cz>
Mon, 7 Oct 2013 13:24:23 +0000 (15:24 +0200)
... to get ready for AMP in GHC 7.10 and silence warning in GHC 7.8.

Keeping join would be quite a hassle. We need to silence warning in GHC
7.8, but we cannot say
  import Prelude hiding (....., join)
because join is not exported untiil 7.10. We also do not want to
explicitly list imported names from Prelude, because there are many
(I tried and stopped after a dozen).

We could silence the amp warning in GHC 7.7 - GHC 7.9 and have
conditional Prelude import for base >= 4.8, hiding join in one of them.
Nevertheless, this is too many problems compared to renaming an internal
join function to link.

Data/IntMap/Base.hs
Data/IntMap/Strict.hs
Data/IntSet/Base.hs
Data/Map/Base.hs
Data/Map/Lazy.hs
Data/Map/Strict.hs
Data/Set.hs
Data/Set/Base.hs

index 91e7fe1..1c6448b 100644 (file)
@@ -196,7 +196,7 @@ module Data.IntMap.Base (
     -- * Utility
     , natFromInt
     , intFromNat
-    , join
+    , link
     , bin
     , zero
     , nomatch
@@ -572,12 +572,12 @@ insert :: Key -> a -> IntMap a -> IntMap a
 insert k x t = k `seq`
   case t of
     Bin p m l r
-      | nomatch k p m -> join k (Tip k x) p t
+      | nomatch k p m -> link k (Tip k x) p t
       | zero k m      -> Bin p m (insert k x l) r
       | otherwise     -> Bin p m l (insert k x r)
     Tip ky _
       | k==ky         -> Tip k x
-      | otherwise     -> join k (Tip k x) ky t
+      | otherwise     -> link k (Tip k x) ky t
     Nil -> Tip k x
 
 -- right-biased insertion, used by 'union'
@@ -610,12 +610,12 @@ insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
 insertWithKey f k x t = k `seq`
   case t of
     Bin p m l r
-      | nomatch k p m -> join k (Tip k x) p t
+      | nomatch k p m -> link k (Tip k x) p t
       | zero k m      -> Bin p m (insertWithKey f k x l) r
       | otherwise     -> Bin p m l (insertWithKey f k x r)
     Tip ky y
       | k==ky         -> Tip k (f k x y)
-      | otherwise     -> join k (Tip k x) ky t
+      | otherwise     -> link k (Tip k x) ky t
     Nil -> Tip k x
 
 -- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)
@@ -637,12 +637,12 @@ insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> (Maybe a,
 insertLookupWithKey f k x t = k `seq`
   case t of
     Bin p m l r
-      | nomatch k p m -> (Nothing,join k (Tip k x) p t)
+      | nomatch k p m -> (Nothing,link k (Tip k x) p t)
       | zero k m      -> let (found,l') = insertLookupWithKey f k x l in (found,Bin p m l' r)
       | otherwise     -> let (found,r') = insertLookupWithKey f k x r in (found,Bin p m l r')
     Tip ky y
       | k==ky         -> (Just y,Tip k (f k x y))
-      | otherwise     -> (Nothing,join k (Tip k x) ky t)
+      | otherwise     -> (Nothing,link k (Tip k x) ky t)
     Nil -> (Nothing,Tip k x)
 
 
@@ -762,7 +762,7 @@ alter f k t = k `seq`
     Bin p m l r
       | nomatch k p m -> case f Nothing of
                            Nothing -> t
-                           Just x -> join k (Tip k x) p t
+                           Just x -> link k (Tip k x) p t
       | zero k m      -> bin p m (alter f k l) r
       | otherwise     -> bin p m l (alter f k r)
     Tip ky y
@@ -770,7 +770,7 @@ alter f k t = k `seq`
                            Just x -> Tip ky x
                            Nothing -> Nil
       | otherwise     -> case f Nothing of
-                           Just x -> join k (Tip k x) ky t
+                           Just x -> link k (Tip k x) ky t
                            Nothing -> Tip ky y
     Nil               -> case f Nothing of
                            Just x -> Tip k x
@@ -956,39 +956,39 @@ mergeWithKey' bin' f g1 g2 = go
       | shorter m1 m2  = merge1
       | shorter m2 m1  = merge2
       | p1 == p2       = bin' p1 m1 (go l1 l2) (go r1 r2)
-      | otherwise      = maybe_join p1 (g1 t1) p2 (g2 t2)
+      | otherwise      = maybe_link p1 (g1 t1) p2 (g2 t2)
       where
-        merge1 | nomatch p2 p1 m1  = maybe_join p1 (g1 t1) p2 (g2 t2)
+        merge1 | nomatch p2 p1 m1  = maybe_link p1 (g1 t1) p2 (g2 t2)
                | zero p2 m1        = bin' p1 m1 (go l1 t2) (g1 r1)
                | otherwise         = bin' p1 m1 (g1 l1) (go r1 t2)
-        merge2 | nomatch p1 p2 m2  = maybe_join p1 (g1 t1) p2 (g2 t2)
+        merge2 | nomatch p1 p2 m2  = maybe_link p1 (g1 t1) p2 (g2 t2)
                | zero p1 m2        = bin' p2 m2 (go t1 l2) (g2 r2)
                | otherwise         = bin' p2 m2 (g2 l2) (go t1 r2)
 
     go t1'@(Bin _ _ _ _) t2'@(Tip k2' _) = merge t2' k2' t1'
-      where merge t2 k2 t1@(Bin p1 m1 l1 r1) | nomatch k2 p1 m1 = maybe_join p1 (g1 t1) k2 (g2 t2)
+      where merge t2 k2 t1@(Bin p1 m1 l1 r1) | nomatch k2 p1 m1 = maybe_link p1 (g1 t1) k2 (g2 t2)
                                              | zero k2 m1 = bin' p1 m1 (merge t2 k2 l1) (g1 r1)
                                              | otherwise  = bin' p1 m1 (g1 l1) (merge t2 k2 r1)
             merge t2 k2 t1@(Tip k1 _) | k1 == k2 = f t1 t2
-                                      | otherwise = maybe_join k1 (g1 t1) k2 (g2 t2)
+                                      | otherwise = maybe_link k1 (g1 t1) k2 (g2 t2)
             merge t2 _  Nil = g2 t2
 
     go t1@(Bin _ _ _ _) Nil = g1 t1
 
     go t1'@(Tip k1' _) t2' = merge t1' k1' t2'
-      where merge t1 k1 t2@(Bin p2 m2 l2 r2) | nomatch k1 p2 m2 = maybe_join k1 (g1 t1) p2 (g2 t2)
+      where merge t1 k1 t2@(Bin p2 m2 l2 r2) | nomatch k1 p2 m2 = maybe_link k1 (g1 t1) p2 (g2 t2)
                                              | zero k1 m2 = bin' p2 m2 (merge t1 k1 l2) (g2 r2)
                                              | otherwise  = bin' p2 m2 (g2 l2) (merge t1 k1 r2)
             merge t1 k1 t2@(Tip k2 _) | k1 == k2 = f t1 t2
-                                      | otherwise = maybe_join k1 (g1 t1) k2 (g2 t2)
+                                      | otherwise = maybe_link k1 (g1 t1) k2 (g2 t2)
             merge t1 _  Nil = g1 t1
 
     go Nil t2 = g2 t2
 
-    maybe_join _ Nil _ t2 = t2
-    maybe_join _ t1 _ Nil = t1
-    maybe_join p1 t1 p2 t2 = join p1 t1 p2 t2
-    {-# INLINE maybe_join #-}
+    maybe_link _ Nil _ t2 = t2
+    maybe_link _ t1 _ Nil = t1
+    maybe_link p1 t1 p2 t2 = link p1 t1 p2 t2
+    {-# INLINE maybe_link #-}
 {-# INLINE mergeWithKey' #-}
 
 {--------------------------------------------------------------------
@@ -1923,7 +1923,7 @@ fromDistinctAscList (z0 : zs0) = work z0 zs0 Nada
                  else work z zs (Push px tx stk)
 
     finish _  t  Nada = t
-    finish px tx (Push py ty stk) = finish p (join py ty px tx) stk
+    finish px tx (Push py ty stk) = finish p (link py ty px tx) stk
         where m = branchMask px py
               p = mask px m
 
@@ -2004,16 +2004,16 @@ INSTANCE_TYPEABLE1(IntMap,intMapTc,"IntMap")
   Helpers
 --------------------------------------------------------------------}
 {--------------------------------------------------------------------
-  Join
+  Link
 --------------------------------------------------------------------}
-join :: Prefix -> IntMap a -> Prefix -> IntMap a -> IntMap a
-join p1 t1 p2 t2
+link :: Prefix -> IntMap a -> Prefix -> IntMap a -> IntMap a
+link p1 t1 p2 t2
   | zero p1 m = Bin p m t1 t2
   | otherwise = Bin p m t2 t1
   where
     m = branchMask p1 p2
     p = mask p1 m
-{-# INLINE join #-}
+{-# INLINE link #-}
 
 {--------------------------------------------------------------------
   @bin@ assures that we never have empty trees within a tree.
index bd9e179..9b42c4f 100644 (file)
@@ -328,12 +328,12 @@ insert :: Key -> a -> IntMap a -> IntMap a
 insert k x t = k `seq` x `seq`
   case t of
     Bin p m l r
-      | nomatch k p m -> join k (Tip k x) p t
+      | nomatch k p m -> link k (Tip k x) p t
       | zero k m      -> Bin p m (insert k x l) r
       | otherwise     -> Bin p m l (insert k x r)
     Tip ky _
       | k==ky         -> Tip k x
-      | otherwise     -> join k (Tip k x) ky t
+      | otherwise     -> link k (Tip k x) ky t
     Nil -> Tip k x
 
 -- right-biased insertion, used by 'union'
@@ -369,12 +369,12 @@ insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a
 insertWithKey f k x t = k `seq`
   case t of
     Bin p m l r
-      | nomatch k p m -> join k (singleton k x) p t
+      | nomatch k p m -> link k (singleton k x) p t
       | zero k m      -> Bin p m (insertWithKey f k x l) r
       | otherwise     -> Bin p m l (insertWithKey f k x r)
     Tip ky y
       | k==ky         -> Tip k $! f k x y
-      | otherwise     -> join k (singleton k x) ky t
+      | otherwise     -> link k (singleton k x) ky t
     Nil -> singleton k x
 
 -- | /O(min(n,W))/. The expression (@'insertLookupWithKey' f k x map@)
@@ -398,12 +398,12 @@ insertLookupWithKey f0 k0 x0 t0 = k0 `seq` toPair $ go f0 k0 x0 t0
     go f k x t =
       case t of
         Bin p m l r
-          | nomatch k p m -> Nothing :*: join k (singleton k x) p t
+          | nomatch k p m -> Nothing :*: link k (singleton k x) p t
           | zero k m      -> let (found :*: l') = go f k x l in (found :*: Bin p m l' r)
           | otherwise     -> let (found :*: r') = go f k x r in (found :*: Bin p m l r')
         Tip ky y
           | k==ky         -> (Just y :*: (Tip k $! f k x y))
-          | otherwise     -> (Nothing :*: join k (singleton k x) ky t)
+          | otherwise     -> (Nothing :*: link k (singleton k x) ky t)
         Nil -> Nothing :*: (singleton k x)
 
 
@@ -506,7 +506,7 @@ alter f k t = k `seq`
     Bin p m l r
       | nomatch k p m -> case f Nothing of
                            Nothing -> t
-                           Just x  -> x `seq` join k (Tip k x) p t
+                           Just x  -> x `seq` link k (Tip k x) p t
       | zero k m      -> bin p m (alter f k l) r
       | otherwise     -> bin p m l (alter f k r)
     Tip ky y
@@ -514,7 +514,7 @@ alter f k t = k `seq`
                            Just  x -> x `seq` Tip ky x
                            Nothing -> Nil
       | otherwise     -> case f Nothing of
-                           Just x  -> x `seq` join k (Tip k x) ky t
+                           Just x  -> x `seq` link k (Tip k x) ky t
                            Nothing -> t
     Nil               -> case f Nothing of
                            Just x  -> x `seq` Tip k x
@@ -970,7 +970,7 @@ fromDistinctAscList (z0 : zs0) = work z0 zs0 Nada
                  else work z zs (Push px tx stk)
 
     finish _  t  Nada = t
-    finish px tx (Push py ty stk) = finish p (join py ty px tx) stk
+    finish px tx (Push py ty stk) = finish p (link py ty px tx) stk
         where m = branchMask px py
               p = mask px m
 
index 9315b08..9e0320b 100644 (file)
@@ -458,12 +458,12 @@ insertBM :: Prefix -> BitMap -> IntSet -> IntSet
 insertBM kx bm t = kx `seq` bm `seq`
   case t of
     Bin p m l r
-      | nomatch kx p m -> join kx (Tip kx bm) p t
+      | nomatch kx p m -> link kx (Tip kx bm) p t
       | zero kx m      -> Bin p m (insertBM kx bm l) r
       | otherwise      -> Bin p m l (insertBM kx bm r)
     Tip kx' bm'
       | kx' == kx -> Tip kx' (bm .|. bm')
-      | otherwise -> join kx (Tip kx bm) kx' t
+      | otherwise -> link kx (Tip kx bm) kx' t
     Nil -> Tip kx bm
 
 -- | /O(min(n,W))/. Delete a value in the set. Returns the
@@ -501,13 +501,13 @@ union t1@(Bin p1 m1 l1 r1) t2@(Bin p2 m2 l2 r2)
   | shorter m1 m2  = union1
   | shorter m2 m1  = union2
   | p1 == p2       = Bin p1 m1 (union l1 l2) (union r1 r2)
-  | otherwise      = join p1 t1 p2 t2
+  | otherwise      = link p1 t1 p2 t2
   where
-    union1  | nomatch p2 p1 m1  = join p1 t1 p2 t2
+    union1  | nomatch p2 p1 m1  = link p1 t1 p2 t2
             | zero p2 m1        = Bin p1 m1 (union l1 t2) r1
             | otherwise         = Bin p1 m1 l1 (union r1 t2)
 
-    union2  | nomatch p1 p2 m2  = join p1 t1 p2 t2
+    union2  | nomatch p1 p2 m2  = link p1 t1 p2 t2
             | zero p1 m2        = Bin p2 m2 (union t1 l2) r2
             | otherwise         = Bin p2 m2 l2 (union t1 r2)
 
@@ -1019,7 +1019,7 @@ fromDistinctAscList (z0 : zs0) = work (prefixOf z0) (bitmapOf z0) zs0 Nada
                  else work (prefixOf z) (bitmapOf z) zs (Push px tx stk)
 
     finish _  t  Nada = t
-    finish px tx (Push py ty stk) = finish p (join py ty px tx) stk
+    finish px tx (Push py ty stk) = finish p (link py ty px tx) stk
         where m = branchMask px py
               p = mask px m
 
@@ -1179,16 +1179,16 @@ withEmpty bars = "   ":bars
   Helpers
 --------------------------------------------------------------------}
 {--------------------------------------------------------------------
-  Join
+  Link
 --------------------------------------------------------------------}
-join :: Prefix -> IntSet -> Prefix -> IntSet -> IntSet
-join p1 t1 p2 t2
+link :: Prefix -> IntSet -> Prefix -> IntSet -> IntSet
+link p1 t1 p2 t2
   | zero p1 m = Bin p m t1 t2
   | otherwise = Bin p m t2 t1
   where
     m = branchMask p1 p2
     p = mask p1 m
-{-# INLINE join #-}
+{-# INLINE link #-}
 
 {--------------------------------------------------------------------
   @bin@ assures that we never have empty trees within a tree.
index fa2fa6a..36da982 100644 (file)
@@ -251,7 +251,7 @@ module Data.Map.Base (
     , balanceL
     , balanceR
     , delta
-    , join
+    , link
     , insertMax
     , merge
     , glue
@@ -1221,10 +1221,10 @@ union t1 t2 = hedgeUnion NothingS NothingS t1 t2
 -- left-biased hedge union
 hedgeUnion :: Ord a => MaybeS a -> MaybeS a -> Map a b -> Map a b -> Map a b
 hedgeUnion _   _   t1  Tip = t1
-hedgeUnion blo bhi Tip (Bin _ kx x l r) = join kx x (filterGt blo l) (filterLt bhi r)
+hedgeUnion blo bhi Tip (Bin _ kx x l r) = link kx x (filterGt blo l) (filterLt bhi r)
 hedgeUnion _   _   t1  (Bin _ kx x Tip Tip) = insertR kx x t1  -- According to benchmarks, this special case increases
                                                               -- performance up to 30%. It does not help in difference or intersection.
-hedgeUnion blo bhi (Bin _ kx x l r) t2 = join kx x (hedgeUnion blo bmi l (trim blo bmi t2))
+hedgeUnion blo bhi (Bin _ kx x l r) t2 = link kx x (hedgeUnion blo bmi l (trim blo bmi t2))
                                                    (hedgeUnion bmi bhi r (trim bmi bhi t2))
   where bmi = JustS kx
 #if __GLASGOW_HASKELL__ >= 700
@@ -1276,7 +1276,7 @@ difference t1 t2   = hedgeDiff NothingS NothingS t1 t2
 
 hedgeDiff :: Ord a => MaybeS a -> MaybeS a -> Map a b -> Map a c -> Map a b
 hedgeDiff _   _   Tip              _ = Tip
-hedgeDiff blo bhi (Bin _ kx x l r) Tip = join kx x (filterGt blo l) (filterLt bhi r)
+hedgeDiff blo bhi (Bin _ kx x l r) Tip = link kx x (filterGt blo l) (filterLt bhi r)
 hedgeDiff blo bhi t (Bin _ kx _ l r) = merge (hedgeDiff blo bmi (trim blo bmi t) l)
                                              (hedgeDiff bmi bhi (trim bmi bhi t) r)
   where bmi = JustS kx
@@ -1343,7 +1343,7 @@ hedgeInt _ _ _   Tip = Tip
 hedgeInt _ _ Tip _   = Tip
 hedgeInt blo bhi (Bin _ kx x l r) t2 = let l' = hedgeInt blo bmi l (trim blo bmi t2)
                                            r' = hedgeInt bmi bhi r (trim bmi bhi t2)
-                                       in if kx `member` t2 then join kx x l' r' else merge l' r'
+                                       in if kx `member` t2 then link kx x l' r' else merge l' r'
   where bmi = JustS kx
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE hedgeInt #-}
@@ -1424,18 +1424,18 @@ mergeWithKey f g1 g2 = go
     go t1 t2 = hedgeMerge NothingS NothingS t1 t2
 
     hedgeMerge _   _   t1  Tip = g1 t1
-    hedgeMerge blo bhi Tip (Bin _ kx x l r) = g2 $ join kx x (filterGt blo l) (filterLt bhi r)
+    hedgeMerge blo bhi Tip (Bin _ kx x l r) = g2 $ link kx x (filterGt blo l) (filterLt bhi r)
     hedgeMerge blo bhi (Bin _ kx x l r) t2 = let l' = hedgeMerge blo bmi l (trim blo bmi t2)
                                                  (found, trim_t2) = trimLookupLo kx bhi t2
                                                  r' = hedgeMerge bmi bhi r trim_t2
                                              in case found of
                                                   Nothing -> case g1 (singleton kx x) of
                                                                Tip -> merge l' r'
-                                                               (Bin _ _ x' Tip Tip) -> join kx x' l' r'
+                                                               (Bin _ _ x' Tip Tip) -> link kx x' l' r'
                                                                _ -> error "mergeWithKey: Given function only1 does not fulfil required conditions (see documentation)"
                                                   Just x2 -> case f kx x x2 of
                                                                Nothing -> merge l' r'
-                                                               Just x' -> join kx x' l' r'
+                                                               Just x' -> link kx x' l' r'
       where bmi = JustS kx
 {-# INLINE mergeWithKey #-}
 
@@ -1543,7 +1543,7 @@ filter p m
 filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
 filterWithKey _ Tip = Tip
 filterWithKey p (Bin _ kx x l r)
-  | p kx x    = join kx x (filterWithKey p l) (filterWithKey p r)
+  | p kx x    = link kx x (filterWithKey p l) (filterWithKey p r)
   | otherwise = merge (filterWithKey p l) (filterWithKey p r)
 
 -- | /O(n)/. Partition the map according to a predicate. The first
@@ -1571,8 +1571,8 @@ partitionWithKey p0 t0 = toPair $ go p0 t0
   where
     go _ Tip = (Tip :*: Tip)
     go p (Bin _ kx x l r)
-      | p kx x    = join kx x l1 r1 :*: merge l2 r2
-      | otherwise = merge l1 r1 :*: join kx x l2 r2
+      | p kx x    = link kx x l1 r1 :*: merge l2 r2
+      | otherwise = merge l1 r1 :*: link kx x l2 r2
       where
         (l1 :*: l2) = go p l
         (r1 :*: r2) = go p r
@@ -1593,7 +1593,7 @@ mapMaybe f = mapMaybeWithKey (\_ x -> f x)
 mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
 mapMaybeWithKey _ Tip = Tip
 mapMaybeWithKey f (Bin _ kx x l r) = case f kx x of
-  Just y  -> join kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)
+  Just y  -> link kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)
   Nothing -> merge (mapMaybeWithKey f l) (mapMaybeWithKey f r)
 
 -- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
@@ -1623,8 +1623,8 @@ mapEitherWithKey f0 t0 = toPair $ go f0 t0
   where
     go _ Tip = (Tip :*: Tip)
     go f (Bin _ kx x l r) = case f kx x of
-      Left y  -> join kx y l1 r1 :*: merge l2 r2
-      Right z -> merge l1 r1 :*: join kx z l2 r2
+      Left y  -> link kx y l1 r1 :*: merge l2 r2
+      Right z -> merge l1 r1 :*: link kx z l2 r2
      where
         (l1 :*: l2) = go f l
         (r1 :*: r2) = go f r
@@ -1974,8 +1974,8 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = fromList' (Bin 1 kx0 x0 Tip T
     go _ t [(kx, x)] = insertMax kx x t
     go s l xs@((kx, x) : xss) | not_ordered kx xss = fromList' l xs
                               | otherwise = case create s xss of
-                                  (r, ys, []) -> go (s `shiftL` 1) (join kx x l r) ys
-                                  (r, _,  ys) -> fromList' (join kx x l r) ys
+                                  (r, ys, []) -> go (s `shiftL` 1) (link kx x l r) ys
+                                  (r, _,  ys) -> fromList' (link kx x l r) ys
 
     -- The create is returning a triple (tree, xs, ys). Both xs and ys
     -- represent not yet processed elements and only one of them can be nonempty.
@@ -1992,7 +1992,7 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = fromList' (Bin 1 kx0 x0 Tip T
                       (l, [(ky, y)], zs) -> (insertMax ky y l, [], zs)
                       (l, ys@((ky, y):yss), _) | not_ordered ky yss -> (l, [], ys)
                                                | otherwise -> case create (s `shiftR` 1) yss of
-                                                   (r, zs, ws) -> (join ky y l r, zs, ws)
+                                                   (r, zs, ws) -> (link ky y l r, zs, ws)
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE fromList #-}
 #endif
@@ -2164,7 +2164,7 @@ fromDistinctAscList ((kx0, x0) : xs0) = go (1::Int) (Bin 1 kx0 x0 Tip Tip) xs0
     STRICT_1_OF_3(go)
     go _ t [] = t
     go s l ((kx, x) : xs) = case create s xs of
-                              (r, ys) -> go (s `shiftL` 1) (join kx x l r) ys
+                              (r, ys) -> go (s `shiftL` 1) (link kx x l r) ys
 
     STRICT_1_OF_2(create)
     create _ [] = (Tip, [])
@@ -2173,7 +2173,7 @@ fromDistinctAscList ((kx0, x0) : xs0) = go (1::Int) (Bin 1 kx0 x0 Tip Tip) xs0
       | otherwise = case create (s `shiftR` 1) xs of
                       res@(_, []) -> res
                       (l, (ky, y):ys) -> case create (s `shiftR` 1) ys of
-                        (r, zs) -> (join ky y l r, zs)
+                        (r, zs) -> (link ky y l r, zs)
 
 
 {--------------------------------------------------------------------
@@ -2254,7 +2254,7 @@ filterGt NothingS t = t
 filterGt (JustS b) t = filter' b t
   where filter' _   Tip = Tip
         filter' b' (Bin _ kx x l r) =
-          case compare b' kx of LT -> join kx x (filter' b' l) r
+          case compare b' kx of LT -> link kx x (filter' b' l) r
                                 EQ -> r
                                 GT -> filter' b' r
 #if __GLASGOW_HASKELL__ >= 700
@@ -2266,7 +2266,7 @@ filterLt NothingS t = t
 filterLt (JustS b) t = filter' b t
   where filter' _   Tip = Tip
         filter' b' (Bin _ kx x l r) =
-          case compare kx b' of LT -> join kx x l (filter' b' r)
+          case compare kx b' of LT -> link kx x l (filter' b' r)
                                 EQ -> l
                                 GT -> filter' b' l
 #if __GLASGOW_HASKELL__ >= 700
@@ -2293,8 +2293,8 @@ split k0 t0 = k0 `seq` toPair $ go k0 t0
       case t of
         Tip            -> (Tip :*: Tip)
         Bin _ kx x l r -> case compare k kx of
-          LT -> let (lt :*: gt) = go k l in lt :*: join kx x gt r
-          GT -> let (lt :*: gt) = go k r in join kx x l lt :*: gt
+          LT -> let (lt :*: gt) = go k l in lt :*: link kx x gt r
+          GT -> let (lt :*: gt) = go k r in link kx x l lt :*: gt
           EQ -> (l :*: r)
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE split #-}
@@ -2315,10 +2315,10 @@ splitLookup k t = k `seq`
     Tip            -> (Tip,Nothing,Tip)
     Bin _ kx x l r -> case compare k kx of
       LT -> let (lt,z,gt) = splitLookup k l
-                gt' = join kx x gt r
+                gt' = link kx x gt r
             in gt' `seq` (lt,z,gt')
       GT -> let (lt,z,gt) = splitLookup k r
-                lt' = join kx x l lt
+                lt' = link kx x l lt
             in lt' `seq` (lt',z,gt)
       EQ -> (l,Just x,r)
 #if __GLASGOW_HASKELL__ >= 700
@@ -2337,7 +2337,7 @@ splitLookup k t = k `seq`
     [balance k x l r] Restores the balance and size.
                       Assumes that the original tree was balanced and
                       that [l] or [r] has changed by at most one element.
-    [join k x l r]    Restores balance and size.
+    [link k x l r]    Restores balance and size.
 
   Furthermore, we can construct a new tree from two trees. Both operations
   assume that all values in [l] < all values in [r] and that [l] and [r]
@@ -2347,7 +2347,7 @@ splitLookup k t = k `seq`
     [merge l r]       Merges two trees and restores balance.
 
   Note: in contrast to Adam's paper, we use (<=) comparisons instead
-  of (<) comparisons in [join], [merge] and [balance].
+  of (<) comparisons in [link], [merge] and [balance].
   Quickcheck (on [difference]) showed that this was necessary in order
   to maintain the invariants. It is quite unsatisfactory that I haven't
   been able to find out why this is actually the case! Fortunately, it
@@ -2355,14 +2355,14 @@ splitLookup k t = k `seq`
 --------------------------------------------------------------------}
 
 {--------------------------------------------------------------------
-  Join
+  Link
 --------------------------------------------------------------------}
-join :: k -> a -> Map k a -> Map k a -> Map k a
-join kx x Tip r  = insertMin kx x r
-join kx x l Tip  = insertMax kx x l
-join kx x l@(Bin sizeL ky y ly ry) r@(Bin sizeR kz z lz rz)
-  | delta*sizeL < sizeR  = balanceL kz z (join kx x l lz) rz
-  | delta*sizeR < sizeL  = balanceR ky y ly (join kx x ry r)
+link :: k -> a -> Map k a -> Map k a -> Map k a
+link kx x Tip r  = insertMin kx x r
+link kx x l Tip  = insertMax kx x l
+link kx x l@(Bin sizeL ky y ly ry) r@(Bin sizeR kz z lz rz)
+  | delta*sizeL < sizeR  = balanceL kz z (link kx x l lz) rz
+  | delta*sizeR < sizeL  = balanceR ky y ly (link kx x ry r)
   | otherwise            = bin kx x l r
 
 
index 1b939f7..98d9232 100644 (file)
@@ -208,7 +208,7 @@ module Data.Map.Lazy (
     -- * Internals
     , bin
     , balanced
-    , join
+    , link
     , merge
 #endif
 
index abafcf3..64b47fc 100644 (file)
@@ -215,7 +215,7 @@ module Data.Map.Strict
     -- * Internals
     , bin
     , balanced
-    , join
+    , link
     , merge
 #endif
     ) where
@@ -842,18 +842,18 @@ mergeWithKey f g1 g2 = go
     go t1 t2 = hedgeMerge NothingS NothingS t1 t2
 
     hedgeMerge _   _   t1  Tip = g1 t1
-    hedgeMerge blo bhi Tip (Bin _ kx x l r) = g2 $ join kx x (filterGt blo l) (filterLt bhi r)
+    hedgeMerge blo bhi Tip (Bin _ kx x l r) = g2 $ link kx x (filterGt blo l) (filterLt bhi r)
     hedgeMerge blo bhi (Bin _ kx x l r) t2 = let l' = hedgeMerge blo bmi l (trim blo bmi t2)
                                                  (found, trim_t2) = trimLookupLo kx bhi t2
                                                  r' = hedgeMerge bmi bhi r trim_t2
                                              in case found of
                                                   Nothing -> case g1 (singleton kx x) of
                                                                Tip -> merge l' r'
-                                                               (Bin _ _ x' Tip Tip) -> join kx x' l' r'
+                                                               (Bin _ _ x' Tip Tip) -> link kx x' l' r'
                                                                _ -> error "mergeWithKey: Given function only1 does not fulfil required conditions (see documentation)"
                                                   Just x2 -> case f kx x x2 of
                                                                Nothing -> merge l' r'
-                                                               Just x' -> x' `seq` join kx x' l' r'
+                                                               Just x' -> x' `seq` link kx x' l' r'
       where bmi = JustS kx
 {-# INLINE mergeWithKey #-}
 
@@ -877,7 +877,7 @@ mapMaybe f = mapMaybeWithKey (\_ x -> f x)
 mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
 mapMaybeWithKey _ Tip = Tip
 mapMaybeWithKey f (Bin _ kx x l r) = case f kx x of
-  Just y  -> y `seq` join kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)
+  Just y  -> y `seq` link kx y (mapMaybeWithKey f l) (mapMaybeWithKey f r)
   Nothing -> merge (mapMaybeWithKey f l) (mapMaybeWithKey f r)
 
 -- | /O(n)/. Map values and separate the 'Left' and 'Right' results.
@@ -907,8 +907,8 @@ mapEitherWithKey f0 t0 = toPair $ go f0 t0
   where
     go _ Tip = (Tip :*: Tip)
     go f (Bin _ kx x l r) = case f kx x of
-      Left y  -> y `seq` (join kx y l1 r1 :*: merge l2 r2)
-      Right z -> z `seq` (merge l1 r1 :*: join kx z l2 r2)
+      Left y  -> y `seq` (link kx y l1 r1 :*: merge l2 r2)
+      Right z -> z `seq` (merge l1 r1 :*: link kx z l2 r2)
      where
         (l1 :*: l2) = go f l
         (r1 :*: r2) = go f r
@@ -1039,8 +1039,8 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = x0 `seq` fromList' (Bin 1 kx0
     go _ t [(kx, x)] = x `seq` insertMax kx x t
     go s l xs@((kx, x) : xss) | not_ordered kx xss = fromList' l xs
                               | otherwise = case create s xss of
-                                  (r, ys, []) -> x `seq` go (s `shiftL` 1) (join kx x l r) ys
-                                  (r, _,  ys) -> x `seq` fromList' (join kx x l r) ys
+                                  (r, ys, []) -> x `seq` go (s `shiftL` 1) (link kx x l r) ys
+                                  (r, _,  ys) -> x `seq` fromList' (link kx x l r) ys
 
     -- The create is returning a triple (tree, xs, ys). Both xs and ys
     -- represent not yet processed elements and only one of them can be nonempty.
@@ -1057,7 +1057,7 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = x0 `seq` fromList' (Bin 1 kx0
                       (l, [(ky, y)], zs) -> y `seq` (insertMax ky y l, [], zs)
                       (l, ys@((ky, y):yss), _) | not_ordered ky yss -> (l, [], ys)
                                                | otherwise -> case create (s `shiftR` 1) yss of
-                                                   (r, zs, ws) -> y `seq` (join ky y l r, zs, ws)
+                                                   (r, zs, ws) -> y `seq` (link ky y l r, zs, ws)
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE fromList #-}
 #endif
@@ -1169,7 +1169,7 @@ fromDistinctAscList ((kx0, x0) : xs0) = x0 `seq` go (1::Int) (Bin 1 kx0 x0 Tip T
     STRICT_1_OF_3(go)
     go _ t [] = t
     go s l ((kx, x) : xs) = case create s xs of
-                              (r, ys) -> x `seq` go (s `shiftL` 1) (join kx x l r) ys
+                              (r, ys) -> x `seq` go (s `shiftL` 1) (link kx x l r) ys
 
     STRICT_1_OF_2(create)
     create _ [] = (Tip, [])
@@ -1178,4 +1178,4 @@ fromDistinctAscList ((kx0, x0) : xs0) = x0 `seq` go (1::Int) (Bin 1 kx0 x0 Tip T
       | otherwise = case create (s `shiftR` 1) xs of
                       res@(_, []) -> res
                       (l, (ky, y):ys) -> case create (s `shiftR` 1) ys of
-                        (r, zs) -> y `seq` (join ky y l r, zs)
+                        (r, zs) -> y `seq` (link ky y l r, zs)
index d9029be..f9397ce 100644 (file)
@@ -132,7 +132,7 @@ module Data.Set (
             -- Internals (for testing)
             , bin
             , balanced
-            , join
+            , link
             , merge
 #endif
             ) where
index 3037717..d902310 100644 (file)
@@ -177,7 +177,7 @@ module Data.Set.Base (
             -- Internals (for testing)
             , bin
             , balanced
-            , join
+            , link
             , merge
             ) where
 
@@ -568,10 +568,10 @@ union t1 t2 = hedgeUnion NothingS NothingS t1 t2
 
 hedgeUnion :: Ord a => MaybeS a -> MaybeS a -> Set a -> Set a -> Set a
 hedgeUnion _   _   t1  Tip = t1
-hedgeUnion blo bhi Tip (Bin _ x l r) = join x (filterGt blo l) (filterLt bhi r)
+hedgeUnion blo bhi Tip (Bin _ x l r) = link x (filterGt blo l) (filterLt bhi r)
 hedgeUnion _   _   t1  (Bin _ x Tip Tip) = insertR x t1   -- According to benchmarks, this special case increases
                                                           -- performance up to 30%. It does not help in difference or intersection.
-hedgeUnion blo bhi (Bin _ x l r) t2 = join x (hedgeUnion blo bmi l (trim blo bmi t2))
+hedgeUnion blo bhi (Bin _ x l r) t2 = link x (hedgeUnion blo bmi l (trim blo bmi t2))
                                              (hedgeUnion bmi bhi r (trim bmi bhi t2))
   where bmi = JustS x
 #if __GLASGOW_HASKELL__ >= 700
@@ -593,7 +593,7 @@ difference t1 t2   = hedgeDiff NothingS NothingS t1 t2
 
 hedgeDiff :: Ord a => MaybeS a -> MaybeS a -> Set a -> Set a -> Set a
 hedgeDiff _   _   Tip           _ = Tip
-hedgeDiff blo bhi (Bin _ x l r) Tip = join x (filterGt blo l) (filterLt bhi r)
+hedgeDiff blo bhi (Bin _ x l r) Tip = link x (filterGt blo l) (filterLt bhi r)
 hedgeDiff blo bhi t (Bin _ x l r) = merge (hedgeDiff blo bmi (trim blo bmi t) l)
                                           (hedgeDiff bmi bhi (trim bmi bhi t) r)
   where bmi = JustS x
@@ -629,7 +629,7 @@ hedgeInt _ _ _   Tip = Tip
 hedgeInt _ _ Tip _   = Tip
 hedgeInt blo bhi (Bin _ x l r) t2 = let l' = hedgeInt blo bmi l (trim blo bmi t2)
                                         r' = hedgeInt bmi bhi r (trim bmi bhi t2)
-                                    in if x `member` t2 then join x l' r' else merge l' r'
+                                    in if x `member` t2 then link x l' r' else merge l' r'
   where bmi = JustS x
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE hedgeInt #-}
@@ -642,7 +642,7 @@ hedgeInt blo bhi (Bin _ x l r) t2 = let l' = hedgeInt blo bmi l (trim blo bmi t2
 filter :: (a -> Bool) -> Set a -> Set a
 filter _ Tip = Tip
 filter p (Bin _ x l r)
-    | p x       = join x (filter p l) (filter p r)
+    | p x       = link x (filter p l) (filter p r)
     | otherwise = merge (filter p l) (filter p r)
 
 -- | /O(n)/. Partition the set into two sets, one with all elements that satisfy
@@ -654,8 +654,8 @@ partition p0 t0 = toPair $ go p0 t0
     go _ Tip = (Tip :*: Tip)
     go p (Bin _ x l r) = case (go p l, go p r) of
       ((l1 :*: l2), (r1 :*: r2))
-        | p x       -> join x l1 r1 :*: merge l2 r2
-        | otherwise -> merge l1 r1 :*: join x l2 r2
+        | p x       -> link x l1 r1 :*: merge l2 r2
+        | otherwise -> merge l1 r1 :*: link x l2 r2
 
 {----------------------------------------------------------------------
   Map
@@ -825,8 +825,8 @@ fromList (x0 : xs0) | not_ordered x0 xs0 = fromList' (Bin 1 x0 Tip Tip) xs0
     go _ t [x] = insertMax x t
     go s l xs@(x : xss) | not_ordered x xss = fromList' l xs
                         | otherwise = case create s xss of
-                            (r, ys, []) -> go (s `shiftL` 1) (join x l r) ys
-                            (r, _,  ys) -> fromList' (join x l r) ys
+                            (r, ys, []) -> go (s `shiftL` 1) (link x l r) ys
+                            (r, _,  ys) -> fromList' (link x l r) ys
 
     -- The create is returning a triple (tree, xs, ys). Both xs and ys
     -- represent not yet processed elements and only one of them can be nonempty.
@@ -843,7 +843,7 @@ fromList (x0 : xs0) | not_ordered x0 xs0 = fromList' (Bin 1 x0 Tip Tip) xs0
                       (l, [y], zs) -> (insertMax y l, [], zs)
                       (l, ys@(y:yss), _) | not_ordered y yss -> (l, [], ys)
                                          | otherwise -> case create (s `shiftR` 1) yss of
-                                                   (r, zs, ws) -> (join y l r, zs, ws)
+                                                   (r, zs, ws) -> (link y l r, zs, ws)
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE fromList #-}
 #endif
@@ -888,7 +888,7 @@ fromDistinctAscList (x0 : xs0) = go (1::Int) (Bin 1 x0 Tip Tip) xs0
     STRICT_1_OF_3(go)
     go _ t [] = t
     go s l (x : xs) = case create s xs of
-                        (r, ys) -> go (s `shiftL` 1) (join x l r) ys
+                        (r, ys) -> go (s `shiftL` 1) (link x l r) ys
 
     STRICT_1_OF_2(create)
     create _ [] = (Tip, [])
@@ -897,7 +897,7 @@ fromDistinctAscList (x0 : xs0) = go (1::Int) (Bin 1 x0 Tip Tip) xs0
       | otherwise = case create (s `shiftR` 1) xs of
                       res@(_, []) -> res
                       (l, y:ys) -> case create (s `shiftR` 1) ys of
-                        (r, zs) -> (join y l r, zs)
+                        (r, zs) -> (link y l r, zs)
 
 {--------------------------------------------------------------------
   Eq converts the set to a list. In a lazy setting, this
@@ -1001,7 +1001,7 @@ filterGt NothingS t = t
 filterGt (JustS b) t = filter' b t
   where filter' _   Tip = Tip
         filter' b' (Bin _ x l r) =
-          case compare b' x of LT -> join x (filter' b' l) r
+          case compare b' x of LT -> link x (filter' b' l) r
                                EQ -> r
                                GT -> filter' b' r
 #if __GLASGOW_HASKELL__ >= 700
@@ -1013,7 +1013,7 @@ filterLt NothingS t = t
 filterLt (JustS b) t = filter' b t
   where filter' _   Tip = Tip
         filter' b' (Bin _ x l r) =
-          case compare x b' of LT -> join x l (filter' b' r)
+          case compare x b' of LT -> link x l (filter' b' r)
                                EQ -> l
                                GT -> filter' b' l
 #if __GLASGOW_HASKELL__ >= 700
@@ -1032,8 +1032,8 @@ split x0 t0 = toPair $ go x0 t0
     go _ Tip = (Tip :*: Tip)
     go x (Bin _ y l r)
       = case compare x y of
-          LT -> let (lt :*: gt) = go x l in (lt :*: join y gt r)
-          GT -> let (lt :*: gt) = go x r in (join y l lt :*: gt)
+          LT -> let (lt :*: gt) = go x l in (lt :*: link y gt r)
+          GT -> let (lt :*: gt) = go x r in (link y l lt :*: gt)
           EQ -> (l :*: r)
 #if __GLASGOW_HASKELL__ >= 700
 {-# INLINABLE split #-}
@@ -1046,10 +1046,10 @@ splitMember _ Tip = (Tip, False, Tip)
 splitMember x (Bin _ y l r)
    = case compare x y of
        LT -> let (lt, found, gt) = splitMember x l
-                 gt' = join y gt r
+                 gt' = link y gt r
              in gt' `seq` (lt, found, gt')
        GT -> let (lt, found, gt) = splitMember x r
-                 lt' = join y l lt
+                 lt' = link y l lt
              in lt' `seq` (lt', found, gt)
        EQ -> (l, True, r)
 #if __GLASGOW_HASKELL__ >= 700
@@ -1163,7 +1163,7 @@ deleteAt i t = i `seq`
     [balance x l r]   Restores the balance and size.
                       Assumes that the original tree was balanced and
                       that [l] or [r] has changed by at most one element.
-    [join x l r]      Restores balance and size.
+    [link x l r]      Restores balance and size.
 
   Furthermore, we can construct a new tree from two trees. Both operations
   assume that all values in [l] < all values in [r] and that [l] and [r]
@@ -1173,7 +1173,7 @@ deleteAt i t = i `seq`
     [merge l r]       Merges two trees and restores balance.
 
   Note: in contrast to Adam's paper, we use (<=) comparisons instead
-  of (<) comparisons in [join], [merge] and [balance].
+  of (<) comparisons in [link], [merge] and [balance].
   Quickcheck (on [difference]) showed that this was necessary in order
   to maintain the invariants. It is quite unsatisfactory that I haven't
   been able to find out why this is actually the case! Fortunately, it
@@ -1181,14 +1181,14 @@ deleteAt i t = i `seq`
 --------------------------------------------------------------------}
 
 {--------------------------------------------------------------------
-  Join
+  Link
 --------------------------------------------------------------------}
-join :: a -> Set a -> Set a -> Set a
-join x Tip r  = insertMin x r
-join x l Tip  = insertMax x l
-join x l@(Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
-  | delta*sizeL < sizeR  = balanceL z (join x l lz) rz
-  | delta*sizeR < sizeL  = balanceR y ly (join x ry r)
+link :: a -> Set a -> Set a -> Set a
+link x Tip r  = insertMin x r
+link x l Tip  = insertMax x l
+link x l@(Bin sizeL y ly ry) r@(Bin sizeR z lz rz)
+  | delta*sizeL < sizeR  = balanceL z (link x l lz) rz
+  | delta*sizeR < sizeL  = balanceR y ly (link x ry r)
   | otherwise            = bin x l r