remove foldlStrict, generalize type of unions, see #520 (#524)
authorjwaldmann <jwaldmann@users.noreply.github.com>
Fri, 9 Mar 2018 17:18:07 +0000 (18:18 +0100)
committerDavid Feuer <David.Feuer@gmail.com>
Fri, 9 Mar 2018 17:18:07 +0000 (12:18 -0500)
Data/IntMap/Internal.hs
Data/IntMap/Strict.hs
Data/IntSet/Internal.hs
Data/Map/Internal.hs
Data/Map/Strict/Internal.hs
Data/Set/Internal.hs
Utils/Containers/Internal/StrictFold.hs [deleted file]
containers.cabal

index 2ec52fb..8f7792e 100644 (file)
@@ -303,6 +303,7 @@ import Data.Functor.Classes
 import Control.DeepSeq (NFData(rnf))
 import Data.Bits
 import qualified Data.Foldable as Foldable
+import Data.Foldable (Foldable())
 import Data.Maybe (fromMaybe)
 import Data.Typeable
 import Prelude hiding (lookup, map, filter, foldr, foldl, null)
@@ -310,7 +311,6 @@ import Prelude hiding (lookup, map, filter, foldr, foldl, null)
 import Data.IntSet.Internal (Key)
 import qualified Data.IntSet.Internal as IntSet
 import Utils.Containers.Internal.BitUtil
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 
 #if __GLASGOW_HASKELL__
@@ -1003,18 +1003,18 @@ alterF f k m = (<$> f mv) $ \fres ->
 -- > unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
 -- >     == fromList [(3, "B3"), (5, "A3"), (7, "C")]
 
-unions :: [IntMap a] -> IntMap a
+unions :: Foldable f => f (IntMap a) -> IntMap a
 unions xs
-  = foldlStrict union empty xs
+  = Foldable.foldl' union empty xs
 
 -- | The union of a list of maps, with a combining operation.
 --
 -- > unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
 -- >     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
 
-unionsWith :: (a->a->a) -> [IntMap a] -> IntMap a
+unionsWith :: Foldable f => (a->a->a) -> f (IntMap a) -> IntMap a
 unionsWith f ts
-  = foldlStrict (unionWith f) empty ts
+  = Foldable.foldl' (unionWith f) empty ts
 
 -- | /O(n+m)/. The (left-biased) union of two maps.
 -- It prefers the first map when duplicate keys are encountered,
@@ -3031,7 +3031,7 @@ foldlFB = foldlWithKey
 
 fromList :: [(Key,a)] -> IntMap a
 fromList xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x)  = insert k x t
 
@@ -3052,7 +3052,7 @@ fromListWith f xs
 
 fromListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
 fromListWithKey f xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x) = insertWithKey f k x t
 
index 659d66e..bd165a3 100644 (file)
@@ -334,12 +334,13 @@ import Data.IntMap.Internal
 import Data.IntMap.Internal.DeprecatedDebug (showTree, showTreeWith)
 import qualified Data.IntSet.Internal as IntSet
 import Utils.Containers.Internal.BitUtil
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 #if !MIN_VERSION_base(4,8,0)
 import Data.Functor((<$>))
 #endif
 import Control.Applicative (Applicative (..), liftA2)
+import qualified Data.Foldable as Foldable
+import Data.Foldable (Foldable())
 
 {--------------------------------------------------------------------
   Query
@@ -638,9 +639,9 @@ alterF f k m = (<$> f mv) $ \fres ->
 -- > unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
 -- >     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
 
-unionsWith :: (a->a->a) -> [IntMap a] -> IntMap a
+unionsWith :: Foldable f => (a->a->a) -> f (IntMap a) -> IntMap a
 unionsWith f ts
-  = foldlStrict (unionWith f) empty ts
+  = Foldable.foldl' (unionWith f) empty ts
 
 -- | /O(n+m)/. The union with a combining function.
 --
@@ -1049,7 +1050,7 @@ fromSet f (IntSet.Tip kx bm) = buildTree f kx bm (IntSet.suffixBitMask + 1)
 
 fromList :: [(Key,a)] -> IntMap a
 fromList xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x)  = insert k x t
 
@@ -1069,7 +1070,7 @@ fromListWith f xs
 
 fromListWithKey :: (Key -> a -> a -> a) -> [(Key,a)] -> IntMap a
 fromListWithKey f xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x) = insertWithKey f k x t
 
index 3772bcd..4f004b2 100644 (file)
@@ -201,7 +201,6 @@ import Data.Typeable
 import Prelude hiding (filter, foldr, foldl, null, map)
 
 import Utils.Containers.Internal.BitUtil
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 
 #if __GLASGOW_HASKELL__
@@ -217,6 +216,8 @@ import qualified GHC.Exts as GHCExts
 import GHC.Prim (indexInt8OffAddr#)
 #endif
 
+import qualified Data.Foldable as Foldable
+import Data.Foldable (Foldable())
 
 infixl 9 \\{-This comment teaches CPP correct behaviour -}
 
@@ -499,9 +500,9 @@ deleteBM _ _ Nil = Nil
   Union
 --------------------------------------------------------------------}
 -- | The union of a list of sets.
-unions :: [IntSet] -> IntSet
+unions :: Foldable f => f IntSet -> IntSet
 unions xs
-  = foldlStrict union empty xs
+  = Foldable.foldl' union empty xs
 
 
 -- | /O(n+m)/. The union of two sets.
@@ -1044,7 +1045,7 @@ foldlFB = foldl
 -- | /O(n*min(n,W))/. Create a set from a list of integers.
 fromList :: [Key] -> IntSet
 fromList xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t x  = insert x t
 
index e0f7592..d0c1b97 100644 (file)
@@ -378,13 +378,13 @@ import Control.Applicative (Const (..))
 import Control.DeepSeq (NFData(rnf))
 import Data.Bits (shiftL, shiftR)
 import qualified Data.Foldable as Foldable
+import Data.Foldable (Foldable())
 import Data.Typeable
 import Prelude hiding (lookup, map, filter, foldr, foldl, null, splitAt, take, drop)
 
 import qualified Data.Set.Internal as Set
 import Data.Set.Internal (Set)
 import Utils.Containers.Internal.PtrEquality (ptrEq)
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 import Utils.Containers.Internal.StrictMaybe
 import Utils.Containers.Internal.BitQueue
@@ -1782,9 +1782,9 @@ maxView t = case maxViewWithKey t of
 -- > unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
 -- >     == fromList [(3, "B3"), (5, "A3"), (7, "C")]
 
-unions :: Ord k => [Map k a] -> Map k a
+unions :: (Foldable f, Ord k) => f (Map k a) -> Map k a
 unions ts
-  = foldlStrict union empty ts
+  = Foldable.foldl' union empty ts
 #if __GLASGOW_HASKELL__
 {-# INLINABLE unions #-}
 #endif
@@ -1795,9 +1795,9 @@ unions ts
 -- > unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
 -- >     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
 
-unionsWith :: Ord k => (a->a->a) -> [Map k a] -> Map k a
+unionsWith :: (Foldable f, Ord k) => (a->a->a) -> f (Map k a) -> Map k a
 unionsWith f ts
-  = foldlStrict (unionWith f) empty ts
+  = Foldable.foldl' (unionWith f) empty ts
 #if __GLASGOW_HASKELL__
 {-# INLINABLE unionsWith #-}
 #endif
@@ -3348,7 +3348,7 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = fromList' (Bin 1 kx0 x0 Tip T
     not_ordered kx ((ky,_) : _) = kx >= ky
     {-# INLINE not_ordered #-}
 
-    fromList' t0 xs = foldlStrict ins t0 xs
+    fromList' t0 xs = Foldable.foldl' ins t0 xs
       where ins t (k,x) = insert k x t
 
     go !_ t [] = t
@@ -3397,7 +3397,7 @@ fromListWith f xs
 
 fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> Map k a
 fromListWithKey f xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x) = insertWithKey f k x t
 #if __GLASGOW_HASKELL__
index 4fc3eb7..a0bced8 100644 (file)
@@ -406,7 +406,6 @@ import Control.Applicative (Applicative (..), (<$>))
 #endif
 import qualified Data.Set.Internal as Set
 import qualified Data.Map.Internal as L
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 
 import Data.Bits (shiftL, shiftR)
@@ -418,6 +417,8 @@ import Data.Coerce
 import Data.Functor.Identity (Identity (..))
 #endif
 
+import qualified Data.Foldable as Foldable
+import Data.Foldable (Foldable())
 
 -- $strictness
 --
@@ -951,9 +952,9 @@ updateMaxWithKey f (Bin _ kx x l r)    = balanceL kx x l (updateMaxWithKey f r)
 -- > unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
 -- >     == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
 
-unionsWith :: Ord k => (a->a->a) -> [Map k a] -> Map k a
+unionsWith :: (Foldable f, Ord k) => (a->a->a) -> f (Map k a) -> Map k a
 unionsWith f ts
-  = foldlStrict (unionWith f) empty ts
+  = Foldable.foldl' (unionWith f) empty ts
 #if __GLASGOW_HASKELL__
 {-# INLINABLE unionsWith #-}
 #endif
@@ -1487,7 +1488,7 @@ fromList ((kx0, x0) : xs0) | not_ordered kx0 xs0 = x0 `seq` fromList' (Bin 1 kx0
     not_ordered kx ((ky,_) : _) = kx >= ky
     {-# INLINE not_ordered #-}
 
-    fromList' t0 xs = foldlStrict ins t0 xs
+    fromList' t0 xs = Foldable.foldl' ins t0 xs
       where ins t (k,x) = insert k x t
 
     go !_ t [] = t
@@ -1536,7 +1537,7 @@ fromListWith f xs
 
 fromListWithKey :: Ord k => (k -> a -> a -> a) -> [(k,a)] -> Map k a
 fromListWithKey f xs
-  = foldlStrict ins empty xs
+  = Foldable.foldl' ins empty xs
   where
     ins t (k,x) = insertWithKey f k x t
 #if __GLASGOW_HASKELL__
index 5800d98..4470bd1 100644 (file)
@@ -246,7 +246,6 @@ import Data.Foldable (Foldable (foldMap))
 import Data.Typeable
 import Control.DeepSeq (NFData(rnf))
 
-import Utils.Containers.Internal.StrictFold
 import Utils.Containers.Internal.StrictPair
 import Utils.Containers.Internal.PtrEquality
 
@@ -705,8 +704,8 @@ deleteMax Tip             = Tip
   Union.
 --------------------------------------------------------------------}
 -- | The union of a list of sets: (@'unions' == 'foldl' 'union' 'empty'@).
-unions :: Ord a => [Set a] -> Set a
-unions = foldlStrict union empty
+unions :: (Foldable f, Ord a) => f (Set a) -> Set a
+unions = Foldable.foldl' union empty
 #if __GLASGOW_HASKELL__
 {-# INLINABLE unions #-}
 #endif
@@ -973,7 +972,7 @@ fromList (x0 : xs0) | not_ordered x0 xs0 = fromList' (Bin 1 x0 Tip Tip) xs0
     not_ordered x (y : _) = x >= y
     {-# INLINE not_ordered #-}
 
-    fromList' t0 xs = foldlStrict ins t0 xs
+    fromList' t0 xs = Foldable.foldl' ins t0 xs
       where ins t x = insert x t
 
     go !_ t [] = t
diff --git a/Utils/Containers/Internal/StrictFold.hs b/Utils/Containers/Internal/StrictFold.hs
deleted file mode 100644 (file)
index cba4ffd..0000000
+++ /dev/null
@@ -1,20 +0,0 @@
-{-# LANGUAGE CPP #-}
-#if !defined(TESTING) && __GLASGOW_HASKELL__ >= 703
-{-# LANGUAGE Safe #-}
-#endif
-
-#include "containers.h"
-{-# OPTIONS_HADDOCK hide #-}
-
-module Utils.Containers.Internal.StrictFold (foldlStrict) where
-
--- | Same as regular 'Data.List.foldl'', but marked INLINE so that it is always
--- inlined. This allows further optimization of the call to f, which can be
--- optimized/specialised/inlined.
-
-foldlStrict :: (a -> b -> a) -> a -> [b] -> a
-foldlStrict f = go
-  where
-    go z []     = z
-    go z (x:xs) = let z' = f z x in z' `seq` go z' xs
-{-# INLINE foldlStrict #-}
index a4f2815..6c966e1 100644 (file)
@@ -82,7 +82,6 @@ Library
 
     other-modules:
         Utils.Containers.Internal.State
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictMaybe
         Utils.Containers.Internal.PtrEquality
         Utils.Containers.Internal.Coercions
@@ -209,7 +208,6 @@ benchmark lookupge-intmap
       Data.IntSet.Internal
       LookupGE_IntMap
       Utils.Containers.Internal.BitUtil
-      Utils.Containers.Internal.StrictFold
       Utils.Containers.Internal.StrictPair
   ghc-options: -O2
   cpp-options: -DTESTING
@@ -238,7 +236,6 @@ benchmark lookupge-map
       Utils.Containers.Internal.BitQueue
       Utils.Containers.Internal.BitUtil
       Utils.Containers.Internal.PtrEquality
-      Utils.Containers.Internal.StrictFold
       Utils.Containers.Internal.StrictMaybe
       Utils.Containers.Internal.StrictPair
   ghc-options: -O2
@@ -273,7 +270,6 @@ Test-suite map-lazy-properties
         Utils.Containers.Internal.BitQueue
         Utils.Containers.Internal.BitUtil
         Utils.Containers.Internal.PtrEquality
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictMaybe
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
@@ -307,7 +303,6 @@ Test-suite map-strict-properties
         Utils.Containers.Internal.BitQueue
         Utils.Containers.Internal.BitUtil
         Utils.Containers.Internal.PtrEquality
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictMaybe
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
@@ -355,7 +350,6 @@ Test-suite set-properties
         Data.Set.Internal
         Utils.Containers.Internal.BitUtil
         Utils.Containers.Internal.PtrEquality
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
     cpp-options: -DTESTING
@@ -385,7 +379,6 @@ Test-suite intmap-lazy-properties
         Data.IntSet.Internal
         IntMapValidity
         Utils.Containers.Internal.BitUtil
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
     cpp-options: -DTESTING
@@ -414,7 +407,6 @@ Test-suite intmap-strict-properties
         Data.IntSet.Internal
         IntMapValidity
         Utils.Containers.Internal.BitUtil
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
     cpp-options: -DTESTING -DSTRICT
@@ -442,7 +434,6 @@ Test-suite intset-properties
         IntSetValidity
         Utils.Containers.Internal.BitUtil
         Utils.Containers.Internal.PtrEquality
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
     cpp-options: -DTESTING
@@ -480,7 +471,6 @@ Test-suite deprecated-properties
         Utils.Containers.Internal.BitQueue
         Utils.Containers.Internal.BitUtil
         Utils.Containers.Internal.PtrEquality
-        Utils.Containers.Internal.StrictFold
         Utils.Containers.Internal.StrictMaybe
         Utils.Containers.Internal.StrictPair
     type: exitcode-stdio-1.0
@@ -549,7 +539,6 @@ test-suite map-strictness-properties
       Utils.Containers.Internal.BitQueue
       Utils.Containers.Internal.BitUtil
       Utils.Containers.Internal.PtrEquality
-      Utils.Containers.Internal.StrictFold
       Utils.Containers.Internal.StrictMaybe
       Utils.Containers.Internal.StrictPair
   type: exitcode-stdio-1.0
@@ -577,7 +566,6 @@ test-suite intmap-strictness-properties
       Data.IntMap.Strict
       Data.IntSet.Internal
       Utils.Containers.Internal.BitUtil
-      Utils.Containers.Internal.StrictFold
       Utils.Containers.Internal.StrictPair
   type: exitcode-stdio-1.0
   other-extensions: CPP, BangPatterns
@@ -602,7 +590,6 @@ test-suite intset-strictness-properties
       Data.IntSet
       Data.IntSet.Internal
       Utils.Containers.Internal.BitUtil
-      Utils.Containers.Internal.StrictFold
       Utils.Containers.Internal.StrictPair
   type: exitcode-stdio-1.0
   other-extensions: CPP, BangPatterns