hashtables-plus 0.1.0 → 0.2.0

raw patch · 4 files changed

+339/−165 lines, 4 filesdep +criterion-plusdep +deepseqdep +hashtables-plusPVP ok

version bump matches the API change (PVP)

Dependencies added: criterion-plus, deepseq, hashtables-plus, lens, mtl, mwc-random, string-conversions, text, th-printf, transformers

API changes (from Hackage documentation)

Files

• benchmarks/Benchmarks.hs +74/−0
• hashtables-plus.cabal +76/−3
• library/HashtablesPlus.hs +181/−156
• library/HashtablesPlus/Prelude.hs +8/−6

@@ -0,0 +1,74 @@++import Benchmarks.Prelude.Basic hiding (group)+import Benchmarks.Prelude.Strings+import Benchmarks.Prelude.Transformers+import qualified CriterionPlus as C+import qualified Benchmarks.Random as R+import qualified HashtablesPlus as H+import qualified Data.HashTable.IO as T++main = do+  gen <- R.newGen+  C.benchmark $ do++    C.standoff "VS Hashtables" $ do+      rows <- liftIO $ replicateM 10000 $ +        (,) <$> R.generateName gen <*> R.generateVariate gen+      liftIO $ evaluate $! rnf rows+      C.subject "HashtablesPlus" $ do+        liftIO $ do+          t :: H.Map H.Linear StrictText Int <- H.new+          forM_ rows $ H.insertFast t+      C.subject "Hashtables" $ do+        liftIO $ do+          t :: T.LinearHashTable StrictText Int <- T.new+          forM_ rows $ uncurry $ T.insert t++    C.standoff "Set/Inserting" $ do+      let +        subject :: +          forall c. (H.Insert c, H.Row c ~ StrictText) => +          c -> Int -> C.Standoff ()+        subject t n = do+          values <- liftIO $ replicateM n $ R.generateName gen+          C.subject (cs $ show n) $ do+            liftIO $ do+              c :: c <- H.new+              forM_ values $ H.insertFast c++      C.group "Sized" $ do+        C.group "Linear" $ do+          mapM_ (subject (undefined :: H.Set H.Linear StrictText)) +                [10000, 9000, 8000]+      C.group "Linear" $ do+        mapM_ (subject (undefined :: H.Set H.Linear StrictText)) +              [10000, 9000, 8000]+      C.group "Cuckoo" $ do+        mapM_ (subject (undefined :: H.Set H.Cuckoo StrictText)) +              [10000, 9000, 8000]+      C.group "Basic" $ do+        mapM_ (subject (undefined :: H.Set H.Basic StrictText)) +              [10000, 9000, 8000]++    C.standoff "Multitable/Inserts" $ do+      rows <- +        liftIO $ forM [10000, 9000, 8000] $ \n -> do+          replicateM n $ (,) <$> R.generateName gen <*> R.generateVariate gen+      liftIO $! evaluate $! rnf $! rows+      C.group "Multimap" $ do+        C.group "Linear" $ do+          forM_ rows (rowsInsertionSubject (undefined :: H.Multimap H.Linear StrictText (H.Set H.Linear Int)))+      C.group "Map" $ do+        C.group "Linear" $ do+          forM_ rows (rowsInsertionSubject (undefined :: H.Map H.Linear StrictText Int))++++rowsInsertionSubject :: +  forall c. (H.Insert c, H.Row c ~ (StrictText, Int)) => +  c -> [H.Row c] -> C.Standoff ()+rowsInsertionSubject _ rows = do+  C.subject (cs $ show $ length $ rows) $ do+    liftIO $ do+      c :: c <- H.new+      forM_ rows $ H.insertFast c

@@ -1,12 +1,13 @@ name:   hashtables-plus version:-  0.1.0+  0.2.0 synopsis:   Extensions for a "hashtables" library description:-  Provides advanced data structures built on top of the ones from the -  \"hashtables\" library: multimap, set, "StableName"-based structures.+  A dome API over the \"hashtables\" library, +  which provides 'null' and 'size' functions of /O(1)/ complexity and+  advanced data structures: multimap, set, "StableName"-based structures. category:   Data, Data Structures homepage:@@ -60,6 +61,7 @@     DataKinds     DefaultSignatures     DeriveDataTypeable+    DeriveFunctor     DeriveGeneric     EmptyDataDecls     FlexibleContexts@@ -76,6 +78,77 @@     NoMonomorphismRestriction     OverloadedStrings     PatternGuards+    ParallelListComp+    QuasiQuotes+    RankNTypes+    RecordWildCards+    ScopedTypeVariables+    StandaloneDeriving+    TemplateHaskell+    TupleSections+    TypeFamilies+    TypeOperators+  default-language:+    Haskell2010+++benchmark benchmarks+  type:             +    exitcode-stdio-1.0+  hs-source-dirs:   +    benchmarks+  main-is:      +    Benchmarks.hs+  ghc-options:+    -O2+    -threaded+    "-with-rtsopts=-N"+  build-depends:+    hashtables-plus,+    -- benchmarking:+    criterion-plus == 0.1.*,+    -- data:+    hashtables == 1.1.*,+    hashable == 1.2.*,+    string-conversions == 0.3.*,+    th-printf == 0.3.*,+    text == 0.11.*,+    -- control:+    mwc-random == 0.13.*,+    lens == 4.*,+    mtl,+    transformers,+    deepseq,+    -- debugging:+    loch-th == 0.2.*,+    placeholders == 0.1.*,+    -- general:+    base >= 4.5 && < 5+  default-extensions:+    Arrows+    BangPatterns+    ConstraintKinds+    DataKinds+    DefaultSignatures+    DeriveDataTypeable+    DeriveFunctor+    DeriveGeneric+    EmptyDataDecls+    FlexibleContexts+    FlexibleInstances+    FunctionalDependencies+    GADTs+    GeneralizedNewtypeDeriving+    ImpredicativeTypes+    LambdaCase+    LiberalTypeSynonyms+    MultiParamTypeClasses+    MultiWayIf+    NoImplicitPrelude+    NoMonomorphismRestriction+    OverloadedStrings+    PatternGuards+    ParallelListComp     QuasiQuotes     RankNTypes     RecordWildCards

@@ -2,14 +2,16 @@ module HashtablesPlus  (   -- * Data Structures-  Table,+  Map,   Set,   HashRefSet,-  MultiTable,+  Multimap,   Sized,-  -- * HashTable Implementations+  -- * Algorithm+  Algorithm,+  -- ** Implementations   -- | -  -- These are aliases of implementations of a class 'HashTable',+  -- Aliases of implementations of a class 'Data.HashTable.Class.HashTable',   -- which provide different performance and memory consumption characteristics.   -- They are used as parameters to data structures.   -- For more info refer to the documentation on aliased types.@@ -23,24 +25,25 @@   MultiKey,   Value,   Collection(..),+  toList,   Lookup(..),-  LookupMulti(..),+  TraverseMulti(..),+  lookupMulti,   Elem(..),   Insert(..),   Delete(..),   Size(..),   Null(..),-  forM_,-  toList, ) where -import HashtablesPlus.Prelude hiding (elem, toList, null, insert, delete, lookup, foldM, forM_)+import HashtablesPlus.Prelude hiding (traverse, elem, toList, null, insert, delete, lookup, foldM, forM_) import qualified HashtablesPlus.HashRef as HR import qualified Data.HashTable.IO as T import qualified Data.HashTable.ST.Basic import qualified Data.HashTable.ST.Cuckoo import qualified Data.HashTable.ST.Linear+import qualified Data.HashTable.Class   -- * Shared Interface@@ -73,19 +76,36 @@   -- Create a new collection.   new :: IO c   -- |-  -- Strictly fold over the rows.-  foldM :: c -> r -> (r -> Row c -> IO r) -> IO r+  -- Traverse thru all the rows of with side effects.+  traverse :: c -> (Row c -> IO ()) -> IO () +-- |+-- /O(n)/.+-- Convert a collection to a list.+toList :: (Collection c) => c -> IO [Row c]+toList c = do+  ref <- newIORef []+  traverse c $ \r -> modifyIORef ref (r:)+  readIORef ref+ class Collection c => Lookup c where   -- |   -- Lookup an item by a unique key.   lookup :: c -> UniqueKey c -> IO (Maybe (Value c)) -class Collection c => LookupMulti c where+class Collection c => TraverseMulti c where   -- |-  -- Lookup multiple items by a non-unique key.-  lookupMulti :: c -> MultiKey c -> IO [Value c]+  -- Traverse items matching a non-unique key.+  traverseMulti :: c -> MultiKey c -> (Value c -> IO ()) -> IO () +-- |+-- Lookup multiple items by a non-unique key.+lookupMulti :: (TraverseMulti c) => c -> MultiKey c -> IO [Value c]+lookupMulti c k = do+  ref <- newIORef []+  traverseMulti c k $ \v -> modifyIORef ref (v:)+  readIORef ref+ class Collection c => Elem c where   -- |   -- Check whether the collection contains a row by the given unique key.@@ -118,40 +138,43 @@  class Collection c => Size c where   -- |-  -- /O(1)/.   -- Get the size of a collection.   size :: c -> IO Int  class Collection c => Null c where   -- |-  -- /O(1)/.   -- Check whether a collection is empty.   null :: c -> IO Bool   default null :: (Size c) => c -> IO Bool   null = fmap (<= 0) . size  -- |--- Traverse thru all the rows of a collection with side effects.-forM_ :: (Collection c) => c -> (Row c -> IO ()) -> IO ()-forM_ c f = foldM c () (\() r -> f r)---- |--- /O(n)/.--- Convert a collection to a list.-toList :: (Collection c) => c -> IO [Row c]-toList c = foldM c [] (\li ro -> return $ ro : li)---- | -- A constraint for values usable as hash table key. type Key k = (Hashable k, Eq k)   --- * 'HashTable' Implementations+-- * Algorithm ------------------------- +-- |+-- An alias to a 'Data.HashTable.Class.HashTable' constraint of the +-- \"hashtables\" library.+type Algorithm = Data.HashTable.Class.HashTable++-- ** Implementations+-------------------------++-- |+-- The fastest, but the most memory-hungry implementation. type Basic = Data.HashTable.ST.Basic.HashTable++-- |+-- The implementation with a medium performance and memory consumption. type Cuckoo = Data.HashTable.ST.Cuckoo.HashTable++-- |+-- The implementation with a low performance, but also a low memory consumption. type Linear = Data.HashTable.ST.Linear.HashTable  @@ -160,41 +183,48 @@ -------------------------  -- | --- A newtype wrapper over a 'HashTable' implementation @t@.+-- A type synonym for an 'T.IOHashTable' with 'Algorithm' @a@. --  -- E.g.: --  -- @--- type CuckooTable k v = 'Table' 'Cuckoo' k v+-- type CuckooTable k v = 'Map' 'Cuckoo' k v -- @-newtype Table t k v = Table (T.IOHashTable t k v)+type Map a k v = a RealWorld k v -type instance Row (Table t k v) = (k, v)-type instance UniqueKey (Table t k v) = k-type instance Value (Table t k v) = v+type instance Row (Map a k v) = (k, v)+type instance UniqueKey (Map a k v) = k+type instance Value (Map a k v) = v -instance (HashTable t, Key k) => Collection (Table t k v) where-  new = Table <$> T.new-  foldM (Table t) z f = T.foldM f z t+instance (Algorithm a, Key k) => Collection (Map a k v) where+  {-# INLINE new #-}+  new = T.new+  {-# INLINE traverse #-}+  traverse = flip T.mapM_ -instance (HashTable t, Key k) => Lookup (Table t k v) where-  lookup (Table t) = T.lookup t+instance (Algorithm a, Key k) => Lookup (Map a k v) where+  {-# INLINE lookup #-}+  lookup t = T.lookup t -instance (HashTable t, Key k) => Elem (Table t k v)+instance (Algorithm a, Key k) => Elem (Map a k v) -instance (HashTable t, Key k) => Insert (Table t k v) where-  insert (Table t) (k, v) = do+instance (Algorithm a, Key k) => Insert (Map a k v) where+  {-# INLINE insert #-}+  insert t (k, v) = do     T.lookup t k >>= \case       Just v' -> return False        Nothing -> T.insert t k v >> return True-  insertFast (Table t) (k, v) = T.insert t k v+  {-# INLINE insertFast #-}+  insertFast t (k, v) = T.insert t k v -instance (HashTable t, Key k) => Delete (Table t k v) where-  delete (Table t) k = do+instance (Algorithm a, Key k) => Delete (Map a k v) where+  {-# INLINE delete #-}+  delete t k = do     T.lookup t k >>= \case       Just v' -> return False        Nothing -> T.delete t k >> return True-  deleteFast (Table t) k = T.delete t k+  {-# INLINE deleteFast #-}+  deleteFast t k = T.delete t k   @@ -208,29 +238,28 @@ -- A set of values,  -- which have instances for 'Eq' and 'Hashable'. -- --- @t@ is the underlying 'HashTable' implementation, --- @a@ is the item.+-- @a@ is the underlying 'Algorithm', +-- @v@ is the item. --  -- E.g.: --  -- @--- type CuckooSet a = 'Set' 'Cuckoo' a+-- type CuckooSet v = 'Set' 'Cuckoo' v -- @-newtype Set t a = Set (T.IOHashTable t a ())+newtype Set a v = Set (T.IOHashTable a v ()) -type instance Row (Set t a) = a-type instance UniqueKey (Set t a) = a-type instance Value (Set t a) = a+type instance Row (Set a v) = v+type instance UniqueKey (Set a v) = v+type instance Value (Set a v) = v -instance (HashTable t, Key a) => Collection (Set t a) where+instance (Algorithm a, Key v) => Collection (Set a v) where   new = Set <$> T.new-  foldM (Set table) z f = T.foldM f' z table where -    f' z (a, _) = f z a+  traverse (Set table) f = traverse table $ f . fst -instance (HashTable t, Key a) => Elem (Set t a) where+instance (Algorithm a, Key v) => Elem (Set a v) where   elem (Set table) a = T.lookup table a >>= return . isJust -instance (HashTable t, Key a) => Insert (Set t a) where+instance (Algorithm a, Key v) => Insert (Set a v) where   insert (Set table) a = do     T.lookup table a >>= \case       Just _ -> return False@@ -239,7 +268,7 @@         return True   insertFast (Set table) a = T.insert table a () -instance (HashTable t, Key a) => Delete (Set t a) where+instance (Algorithm a, Key v) => Delete (Set a v) where   delete (Set table) a = do     T.lookup table a >>= \case       Just _ -> do@@ -254,29 +283,28 @@ -- |  -- A specialized set of 'HR.HashRef's. -- --- @t@ is the underlying 'HashTable' implementation, --- @a@ is the item.+-- @a@ is the underlying 'Algorithm', +-- @v@ is the item. --  -- E.g.: --  -- @--- type LinearHashRefSet a = 'HashRefSet' 'Linear' a+-- type LinearHashRefSet v = 'HashRefSet' 'Linear' v -- @-newtype HashRefSet t a = HashRefSet (T.IOHashTable t (StableName a) a)+newtype HashRefSet a v = HashRefSet (T.IOHashTable a (StableName v) v) -type instance Row (HashRefSet t a) = HR.HashRef a-type instance UniqueKey (HashRefSet t a) = HR.HashRef a-type instance Value (HashRefSet t a) = HR.HashRef a+type instance Row (HashRefSet a v) = HR.HashRef v+type instance UniqueKey (HashRefSet a v) = HR.HashRef v+type instance Value (HashRefSet a v) = HR.HashRef v -instance (HashTable t) => Collection (HashRefSet t a) where+instance (Algorithm a) => Collection (HashRefSet a v) where   new = HashRefSet <$> T.new-  foldM (HashRefSet table) z f = T.foldM f' z table where -    f' z (sn, a) = f z (HR.HashRef sn a)+  traverse (HashRefSet table) f = traverse table $ f . \(sn, a) -> HR.HashRef sn a -instance (HashTable t) => Elem (HashRefSet t a) where+instance (Algorithm a) => Elem (HashRefSet a v) where   elem (HashRefSet table) (HR.HashRef sn a) = T.lookup table sn >>= return . isJust -instance (HashTable t) => Insert (HashRefSet t a) where+instance (Algorithm a) => Insert (HashRefSet a v) where   insert (HashRefSet table) (HR.HashRef sn a) = do     T.lookup table sn >>= \case       Just _ -> return False@@ -285,7 +313,7 @@         return True   insertFast (HashRefSet table) (HR.HashRef sn a) = T.insert table sn a -instance (HashTable t) => Delete (HashRefSet t a) where+instance (Algorithm a) => Delete (HashRefSet a v) where   delete (HashRefSet table) (HR.HashRef sn a) = do     T.lookup table sn >>= \case       Just _ -> do@@ -296,107 +324,53 @@   --- * Sized------------------------------ |--- A wrapper over a 'Collection',--- which adds 'null' and 'size' functions of /O(1)/ complexity.--- --- E.g.:--- --- @--- type SizedLinearTable k v = 'Sized' ('Table' 'Linear' k v)--- @-data Sized c = Sized !c {-# UNPACK #-} !(IORef Int)--type instance Row (Sized c) = Row c-type instance UniqueKey (Sized c) = UniqueKey c-type instance MultiKey (Sized c) = MultiKey c-type instance Value (Sized c) = Value c--instance (Collection c) => Collection (Sized c) where-  new = Sized <$> new <*> newIORef 0-  foldM (Sized c _) = foldM c--instance (Lookup c) => Lookup (Sized c) where-  lookup (Sized c _) a = lookup c a--instance (LookupMulti c) => LookupMulti (Sized c) where-  lookupMulti (Sized c _) k = lookupMulti c k--instance (Elem c) => Elem (Sized c) where-  elem (Sized c _) a = elem c a--instance (Insert c) => Insert (Sized c) where-  insert (Sized c size) a = do-    ok <- insert c a  -    when ok $ modifyIORef size succ-    return ok--instance (Delete c) => Delete (Sized c) where-  delete (Sized c size) a = do-    ok <- delete c a-    when ok $ modifyIORef size pred-    return ok--instance (Collection c) => Size (Sized c) where-  size (Sized _ s) = readIORef s--instance (Collection c) => Null (Sized c)------ * MultiTable+-- * Multimap -------------------------  -- |--- A multitable (or multimap) with underlying 'HashTable' @t@, key @k@ and +-- A multimap with an underlying 'Algorithm' @a@, a key @k@ and  -- a set implementation @s@. --  -- E.g.: --  -- @--- type BasicMultiTable k v = 'MultiTable' 'Basic' k ('Set' 'Basic' v)+-- type BasicMultimap k v = 'Multimap' 'Basic' k ('Set' 'Basic' v) -- @ --  -- If a 'Sized' implementation of set is specified,  -- a more space efficient instance of 'Delete' will be used. E.g.: --  -- @--- MultiTable Basic k ('Sized' (Set Basic v))+-- Multimap Basic k ('Sized' (Set Basic v)) -- @-newtype MultiTable t k s = MultiTable (T.IOHashTable t k s)+newtype Multimap a k s = Multimap (T.IOHashTable a k s) -type instance Row (MultiTable t k s) = (k, Row s)-type instance UniqueKey (MultiTable t k s) = (k, UniqueKey s)-type instance MultiKey (MultiTable t k s) = k-type instance Value (MultiTable t k s) = Value s+type instance Row (Multimap a k s) = (k, Row s)+type instance UniqueKey (Multimap a k s) = (k, UniqueKey s)+type instance MultiKey (Multimap a k s) = k+type instance Value (Multimap a k s) = Value s -instance (HashTable t, Key k, Collection s) => -         Collection (MultiTable t k s) where-  new = MultiTable <$> T.new-  foldM (MultiTable t) z f = T.foldM f' z t where-    f' z (k, s) = foldM s z f'' where-      f'' z v = f z (k, v)+instance (Algorithm a, Key k, Collection s) => +         Collection (Multimap a k s) where+  new = Multimap <$> T.new+  traverse (Multimap t) f = +    traverse t $ \(k, set) -> traverse set $ \v -> f (k, v) -instance (HashTable t, Key k, Collection s, Value s ~ Row s) => -         LookupMulti (MultiTable t k s) where-  lookupMulti (MultiTable t) k = do-    T.lookup t k >>= \case-      Nothing -> return []-      Just s -> toList s+instance (Algorithm a, Key k, Collection s, Value s ~ Row s) => +         TraverseMulti (Multimap a k s) where+  traverseMulti (Multimap t) k f =+    T.lookup t k >>= maybe (return ()) (flip traverse f) -instance (HashTable t, Key k, Elem s) => -         Elem (MultiTable t k s) where-  elem (MultiTable t) (k, v) = do+instance (Algorithm a, Key k, Elem s) => +         Elem (Multimap a k s) where+  elem (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> return False       Just s -> elem s v -instance (HashTable t, Key k, Insert s) => -         Insert (MultiTable t k s) where-  insert (MultiTable t) (k, v) = do+instance (Algorithm a, Key k, Insert s) => +         Insert (Multimap a k s) where+  insert (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> do         s <- new@@ -405,7 +379,7 @@         return True       Just s -> do         insert s v-  insertFast (MultiTable t) (k, v) = do+  insertFast (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> do         s <- new@@ -414,18 +388,18 @@       Just s -> do         insertFast s v -instance (HashTable t, Key k, Delete c) => Delete (MultiTable t k c) where-  delete (MultiTable t) (k, v) = do+instance (Algorithm a, Key k, Delete s) => Delete (Multimap a k s) where+  delete (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> return False       Just s -> delete s v-  deleteFast (MultiTable t) (k, v) = do+  deleteFast (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> return ()       Just s -> deleteFast s v       -instance (HashTable t, Key k, Delete c) => Delete (MultiTable t k (Sized c)) where-  delete (MultiTable t) (k, v) = do+instance (Algorithm a, Key k, Delete s) => Delete (Multimap a k (Sized s)) where+  delete (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> return False       Just s -> do@@ -436,7 +410,7 @@               False -> return ()               True -> T.delete t k             return True-  deleteFast (MultiTable t) (k, v) = do+  deleteFast (Multimap t) (k, v) = do     T.lookup t k >>= \case       Nothing -> return ()       Just s -> do@@ -445,3 +419,54 @@           False -> return ()           True -> T.delete t k       +++-- * Sized+-------------------------++-- |+-- A wrapper over a 'Collection',+-- which adds 'null' and 'size' functions of /O(1)/ complexity.+-- +-- E.g.:+-- +-- @+-- type SizedLinearTable k v = 'Sized' ('Map' 'Linear' k v)+-- @+data Sized c = Sized !c {-# UNPACK #-} !(IORef Int)++type instance Row (Sized c) = Row c+type instance UniqueKey (Sized c) = UniqueKey c+type instance MultiKey (Sized c) = MultiKey c+type instance Value (Sized c) = Value c++instance (Collection c) => Collection (Sized c) where+  new = Sized <$> new <*> newIORef 0+  traverse (Sized c _) = traverse c++instance (Lookup c) => Lookup (Sized c) where+  lookup (Sized c _) a = lookup c a++instance (TraverseMulti c) => TraverseMulti (Sized c) where+  traverseMulti (Sized c _) = traverseMulti c++instance (Elem c) => Elem (Sized c) where+  elem (Sized c _) a = elem c a++instance (Insert c) => Insert (Sized c) where+  insert (Sized c size) a = do+    ok <- insert c a  +    when ok $ modifyIORef size succ+    return ok++instance (Delete c) => Delete (Sized c) where+  delete (Sized c size) a = do+    ok <- delete c a+    when ok $ modifyIORef size pred+    return ok++instance (Collection c) => Size (Sized c) where+  size (Sized _ s) = readIORef s++instance (Collection c) => Null (Sized c)+

@@ -9,6 +9,7 @@ where  -- base+------------------------- import Prelude as Exports hiding (concat, foldr, mapM_, sequence_, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, mapM, sequence, FilePath, id, (.)) import Control.Monad as Exports hiding (mapM_, sequence_, forM_, msum, mapM, sequence, forM) import Control.Applicative as Exports@@ -21,6 +22,7 @@ import Data.Either as Exports import Data.List as Exports hiding (concat, foldr, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, find, maximumBy, minimumBy, mapAccumL, mapAccumR, foldl') import Data.Tuple as Exports+import Data.Function as Exports hiding ((.), id) import Data.Ord as Exports (Down(..)) import Data.String as Exports import Data.Int as Exports@@ -32,6 +34,7 @@ import Text.Read as Exports (readMaybe, readEither) import Control.Exception as Exports hiding (tryJust, try, assert) import Control.Concurrent as Exports hiding (yield)+import System.Mem as Exports import System.Mem.StableName as Exports import System.Timeout as Exports import System.Exit as Exports@@ -39,24 +42,23 @@ import System.IO as Exports (Handle, hClose) import System.IO.Error as Exports import Unsafe.Coerce as Exports-import GHC.Exts as Exports hiding (Any, traceEvent) import GHC.Generics as Exports (Generic) import GHC.IO.Exception as Exports import Data.IORef as Exports import Data.STRef as Exports import Control.Monad.ST as Exports-import Debug.Trace as Exports+import Debug.Trace as Exports hiding (traceM)  -- placeholders+------------------------- import Development.Placeholders as Exports  -- hashable+------------------------- import Data.Hashable as Exports (Hashable(..), hash, hashWithSalt) --- hashtables-import Data.HashTable.Class as Exports (HashTable)--+-- custom+------------------------- import qualified Debug.Trace.LocationTH  traceM :: (Monad m) => String -> m ()