Improve Traversable instance of Map.
authorMilan Straka <fox@ucw.cz>
Sun, 9 Jun 2013 11:38:09 +0000 (13:38 +0200)
committerMilan Straka <fox@ucw.cz>
Sun, 9 Jun 2013 11:38:09 +0000 (13:38 +0200)
Similarly to Foldable instance (commit #29d3fbcc), add a special case in
traverseWithKey when traversing a leaf. In this case, the Tips under the
leaf are not traversed. The speedup is 25%.

See the log of the mentioned commit #29d3fbcc for discussion of
alternative implementations.

Data/IntMap/Base.hs
Data/Map/Base.hs

index 8e21d7c..0e80f26 100644 (file)
@@ -312,6 +312,7 @@ instance Foldable.Foldable IntMap where
 
 instance Traversable IntMap where
     traverse f = traverseWithKey (\_ -> f)
+    {-# INLINE traverse #-}
 
 instance NFData a => NFData (IntMap a) where
     rnf Nil = ()
index 19918b1..30cac67 100644 (file)
@@ -1658,8 +1658,8 @@ traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
 traverseWithKey f = go
   where
     go Tip = pure Tip
-    go (Bin s k v l r)
-      = flip (Bin s k) <$> go l <*> f k v <*> go r
+    go (Bin 1 k v _ _) = (\v' -> Bin 1 k v' Tip Tip) <$> f k v
+    go (Bin s k v l r) = flip (Bin s k) <$> go l <*> f k v <*> go r
 {-# INLINE traverseWithKey #-}
 
 -- | /O(n)/. The function 'mapAccum' threads an accumulating
@@ -2601,6 +2601,7 @@ instance Functor (Map k) where
 
 instance Traversable (Map k) where
   traverse f = traverseWithKey (\_ -> f)
+  {-# INLINE traverse #-}
 
 instance Foldable.Foldable (Map k) where
   fold t = go t