author Milan Straka Tue, 19 Oct 2010 20:20:43 +0000 (20:20 +0000) committer Milan Straka Tue, 19 Oct 2010 20:20:43 +0000 (20:20 +0000)
Benchmarks shows this is a huge win (100% for (:) being
the function, 1000% for (+) being the function).

 Data/IntMap.hs patch | blob | history Data/IntSet.hs patch | blob | history Data/Map.hs patch | blob | history Data/Set.hs patch | blob | history

index bebca26..0cb24af 100644 (file)
@@ -1611,14 +1611,14 @@ foldWithKey
foldr :: (Key -> a -> b -> b) -> b -> IntMap a -> b
foldr f z t
= case t of
-      Bin 0 m l r | m < 0 -> go f (go f z l) r  -- put negative numbers before.
-      Bin _ _ _ _ -> go z t
+      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.
+      Bin _ _ _ _ -> go z t
Tip k x     -> f k x z
Nil         -> z
where
-    go f z (Bin _ _ l r) = go f (go f z r) l
-    go z (Tip k x)     = f k x z
-    go z Nil           = z
+    go z (Bin _ _ l r) = go (go z r) l
+    go z (Tip k x)     = f k x z
+    go z Nil           = z
{-# INLINE foldr #-}

index db84318..559954a 100644 (file)
@@ -751,14 +751,14 @@ map f = fromList . List.map f . toList
fold :: (Int -> b -> b) -> b -> IntSet -> b
fold f z t
= case t of
-      Bin 0 m l r | m < 0 -> go f (go f z l) r  -- put negative numbers before.
-      Bin _ _ _ _ -> go z t
+      Bin 0 m l r | m < 0 -> go (go z l) r  -- put negative numbers before.
+      Bin _ _ _ _ -> go z t
Tip x       -> f x z
Nil         -> z
where
-    go f z (Bin _ _ l r) = go f (go f z r) l
-    go z (Tip x)       = f x z
-    go z Nil           = z
+    go z (Bin _ _ l r) = go (go z r) l
+    go z (Tip x)       = f x z
+    go z Nil           = z
{-# INLINE fold #-}

{--------------------------------------------------------------------
index 9f81ade..bec9893 100644 (file)
@@ -1678,19 +1678,19 @@ foldWithKey = foldrWithKey
-- | /O(n)/. Post-order fold.  The function will be applied from the lowest
-- value to the highest.
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-foldrWithKey = go
+foldrWithKey = go
where
-    go z Tip              = z
-    go f z (Bin _ kx x l r) = go f (f kx x (go f z r)) l
+    go z Tip              = z
+    go z (Bin _ kx x l r) = go (f kx x (go z r)) l
{-# INLINE foldrWithKey #-}

-- | /O(n)/. Pre-order fold.  The function will be applied from the highest
-- value to the lowest.
foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
-foldlWithKey = go
+foldlWithKey = go
where
-    go z Tip              = z
-    go f z (Bin _ kx x l r) = go f (f (go f z l) kx x) r
+    go z Tip              = z
+    go z (Bin _ kx x l r) = go (f (go z l) kx x) r
{-# INLINE foldlWithKey #-}

{-
index 5ed227f..5bd72f0 100644 (file)
@@ -541,10 +541,10 @@ fold = foldr

-- | /O(n)/. Post-order fold.
foldr :: (a -> b -> b) -> b -> Set a -> b
-foldr = go
+foldr = go
where
-    go z Tip           = z
-    go f z (Bin _ x l r) = go f (f x (go f z r)) l
+    go z Tip           = z
+    go z (Bin _ x l r) = go (f x (go z r)) l
{-# INLINE foldr #-}

{--------------------------------------------------------------------