Do not pass f explicitely for fold.
authorMilan Straka <fox@ucw.cz>
Tue, 19 Oct 2010 20:20:43 +0000 (20:20 +0000)
committerMilan Straka <fox@ucw.cz>
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
Data/IntSet.hs
Data/Map.hs
Data/Set.hs

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 #-}
 
 {--------------------------------------------------------------------