generic-trie 0.3.1 → 0.3.2

raw patch · 6 files changed

+439/−57 lines, 6 filesdep +generic-triedep ~basedep ~transformersnew-component:exe:bogusnew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: generic-trie

Dependency ranges changed: base, transformers

API changes (from Hackage documentation)

Files

• CHANGELOG.md +13/−0
• app/Main.hs +4/−0
• generic-trie.cabal +26/−4
• src/Data/GenericTrie.hs +11/−9
• src/Data/GenericTrie/Internal.hs +348/−44
• src/Prelude.hs +37/−0

@@ -1,8 +1,21 @@+0.3.2+-----++* Add a `trieAlter` method, and use it to speed up `alter`, `insert` and+  `delete`.+* Make the `Show` instance user friendly.+* Add support for GHC versions up to 9.4.+* Fix builds on GHC 7.8, and with old `containers` versions.+* Stop pretending to support GHC 7.4 and 7.6. These have not actually worked in+  some time, and it is hard to test on them.+ 0.3.1 -----+ * Improved strictness * GHC 8.4 compatibility  0.3.0.2 -------+ * GHC 8 compatibility

@@ -0,0 +1,4 @@+module Main where++main :: IO ()+main = putStr ""

@@ -1,5 +1,5 @@ name:                generic-trie-version:             0.3.1+version:             0.3.2 synopsis:            A map, where the keys may be complex structured data. description:         This type implements maps where the keys are themselves                      complex structured data.  For example, the keys may be@@ -18,6 +18,17 @@ cabal-version:       >=1.10 homepage:            http://github.com/glguy/tries bug-reports:         http://github.com/glguy/tries/issues+tested-with:         GHC ==7.8.4+                      || ==7.10.3+                      || ==8.0.2+                      || ==8.2.2+                      || ==8.4.2+                      || ==8.6.1+                      || ==8.8.1+                      || ==8.10.7+                      || ==9.0.2+                      || ==9.2.2+                      || ==9.4.2  extra-source-files:   CHANGELOG.md@@ -25,13 +36,24 @@ library   exposed-modules:     Data.GenericTrie,                        Data.GenericTrie.Internal-  build-depends:       base             >= 4.5     && < 4.11,-                       transformers     >= 0.2     && < 0.6,-                       containers       >= 0.4.2.1 && < 0.6+  other-modules:       Prelude+  build-depends:       base             >= 4.7.0.2 && < 4.18,+                       transformers     >= 0.2     && < 0.7,+                       containers       >= 0.4.2.1 && < 0.7   GHC-options:         -O2 -Wall    hs-source-dirs:      src   default-language:    Haskell2010++-- cabal repl seems to choke on the custom prelude if you just+-- run it on the library in the usual way. If you instead say+-- cabal repl bogus, then it works just fine.+executable bogus+  main-is:             Main.hs+  hs-source-dirs:      app+  default-language:    Haskell2010+  build-depends:       base+                     , generic-trie  source-repository head   type: git

@@ -32,6 +32,7 @@   -- * Trie interface     Trie   , TrieKey+  , ShowTrieKey    -- ** Construction   , empty@@ -61,6 +62,7 @@    -- ** Traversing   , traverseWithKey+  , traverseMaybeWithKey   , mapMaybe   , mapMaybeWithKey   , filter@@ -81,7 +83,6 @@   , OrdKey(..)   ) where -import Control.Applicative (Applicative) import Data.List (foldl') import Data.Maybe (isNothing, isJust) import Prelude hiding (lookup, null, filter)@@ -152,6 +153,13 @@ mapMaybeWithKey = trieMapMaybeWithKey {-# INLINE mapMaybeWithKey #-} +-- | Perform an action for each value in a trie and keep the elements+-- of the trie that result in a 'Just' value.+traverseMaybeWithKey :: (TrieKey k, Applicative f)+                     => (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)+traverseMaybeWithKey = trieTraverseMaybeWithKey+{-# INLINE traverseMaybeWithKey #-}+ -- | Filter the values of a trie with the given predicate. filter :: TrieKey k => (a -> Bool) -> Trie k a -> Trie k a filter p = filterWithKey (const p)@@ -194,10 +202,8 @@ -- at the given key, if one exists, and should return a value to insert at -- that location, or 'Nothing' to delete from that location. alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a-alter k f t =-  case f (lookup k t) of-    Just v' -> insert k v' t-    Nothing -> delete k t+alter = trieAlter+{-# INLINE alter #-}  -- | Insert a value at the given key. The combining function is used -- when a value is already stored at that key. The new value is the@@ -223,10 +229,6 @@ -- | Returns 'False' when the 'Trie' has a value stored at the given key. notMember :: TrieKey k => k -> Trie k a -> Bool notMember k t = isNothing (lookup k t)---- | Transform a trie to an association list.-toList :: TrieKey k => Trie k a -> [(k,a)]-toList = foldWithKey (\k v xs -> (k,v) : xs) []  -- | Left-biased union of two tries union :: TrieKey k => Trie k a -> Trie k a -> Trie k a

@@ -7,7 +7,10 @@ {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE Trustworthy #-} -- coerce {-# LANGUAGE CPP #-} -- MProxy on ghc >= 8-+{-# LANGUAGE EmptyCase #-}+#if __GLASGOW_HASKELL__ >= 810+{-# LANGUAGE StandaloneKindSignatures #-}+#endif #if MIN_VERSION_base(4,9,0) {-# LANGUAGE DataKinds #-} -- Meta #endif@@ -15,8 +18,10 @@ -- | Unstable implementation details module Data.GenericTrie.Internal   ( TrieKey(..)+  , ShowTrieKey(..)   , Trie(..)   , OrdKey(..)+  , toList   -- * Generic derivation implementation   , genericTrieNull   , genericTrieMap@@ -25,29 +30,38 @@   , genericInsert   , genericLookup   , genericDelete+  , genericAlter   , genericMapMaybeWithKey   , genericSingleton   , genericEmpty   , genericFoldWithKey   , genericTraverseWithKey+  , genericTraverseMaybeWithKey   , TrieRepDefault   , GTrieKey(..)   , GTrie(..)   ) where -import Control.Applicative (Applicative, liftA2) import Data.Char (chr, ord) import Data.Coerce (coerce)-import Data.Foldable (Foldable) import Data.IntMap (IntMap)+#if MIN_VERSION_base(4,9,0)+import Data.Kind (Type)+#endif import Data.Map (Map) import Data.Maybe (isNothing)-import Data.Traversable (Traversable,traverse) import GHC.Generics import qualified Data.Foldable as Foldable+import qualified Data.Traversable as Traversable import qualified Data.IntMap as IntMap import qualified Data.Map as Map import Prelude+#if MIN_VERSION_base(4,8,0)+import Data.Void (Void)+#endif+#if MIN_VERSION_base(4,8,0)+import Numeric.Natural+#endif  -- | Types that may be used as the key of a 'Trie'. --@@ -56,7 +70,11 @@ class TrieKey k where    -- | Type of the representation of tries for this key.+#if MIN_VERSION_base(4,9,0)+  type TrieRep k :: Type -> Type+#else   type TrieRep k :: * -> *+#endif    -- | Construct an empty trie   trieEmpty :: Trie k a@@ -73,6 +91,9 @@   -- | Delete element from trie   trieDelete :: k -> Trie k a -> Trie k a +  -- | Insert, modify, or remove an element in a trie+  trieAlter :: k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a+   -- | Construct a trie holding a single value   trieSingleton :: k -> a -> Trie k a @@ -82,9 +103,6 @@   -- | Traverse the values stored in a trie   trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b) -  -- | Show the representation of a trie-  trieShowsPrec :: Show a => Int -> Trie k a -> ShowS-   -- | Apply a function to the values of a 'Trie' and keep the elements   -- of the trie that result in a 'Just' value.   trieMapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b@@ -95,6 +113,10 @@   -- | Traverse a trie with a function of both key and value.   trieTraverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b) +  -- | Traverse a trie with a function of both key and value, and keep the elements+  -- of the trie that result in a 'Just' value.+  trieTraverseMaybeWithKey :: Applicative f => (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)+   trieMergeWithKey :: (k -> a -> b -> Maybe c) ->                       (Trie k a -> Trie k c) ->                       (Trie k b -> Trie k c) ->@@ -133,6 +155,11 @@     k -> Trie k a -> Trie k a   trieDelete = genericDelete +  default trieAlter ::+    ( GTrieKey (Rep k), Generic k , TrieRep k ~ TrieRepDefault k) =>+    k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a+  trieAlter = genericAlter+   default trieMap ::     ( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k) =>     (a -> b) -> Trie k a -> Trie k b@@ -143,11 +170,6 @@     (a -> f b) -> Trie k a -> f (Trie k b)   trieTraverse = genericTrieTraverse -  default trieShowsPrec ::-    ( Show a, GTrieKeyShow (Rep k) , TrieRep k ~ TrieRepDefault k) =>-    Int -> Trie k a -> ShowS-  trieShowsPrec = genericTrieShowsPrec-   default trieMapMaybeWithKey ::     ( GTrieKey (Rep k) , Generic k, TrieRep k ~ TrieRepDefault k) =>     (k -> a -> Maybe b) -> Trie k a -> Trie k b@@ -163,6 +185,11 @@     (k -> a -> f b) -> Trie k a -> f (Trie k b)   trieTraverseWithKey = genericTraverseWithKey +  default trieTraverseMaybeWithKey ::+    ( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k, Applicative f) =>+    (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)+  trieTraverseMaybeWithKey = genericTraverseMaybeWithKey+   default trieMergeWithKey ::     ( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k ) =>     (k -> a -> b -> Maybe c) ->@@ -174,7 +201,19 @@ -- | A map from keys of type @k@, to values of type @a@. newtype Trie k a = MkTrie (TrieRep k a) +-- | Transform a trie to an association list.+toList :: TrieKey k => Trie k a -> [(k,a)]+toList = trieFoldWithKey (\k v xs -> (k,v) : xs) [] +class TrieKey k => ShowTrieKey k where+  -- | Show a representation of the internal structure of a trie+  trieShowsPrec :: Show a => Int -> Trie k a -> ShowS+  default trieShowsPrec ::+    ( Show a, GTrieKeyShow (Rep k) , TrieRep k ~ TrieRepDefault k) =>+    Int -> Trie k a -> ShowS+  trieShowsPrec = genericTrieShowsPrec++ ------------------------------------------------------------------------------ -- Manually derived instances for base types ------------------------------------------------------------------------------@@ -185,13 +224,19 @@   trieLookup k (MkTrie x)       = IntMap.lookup k x   trieInsert k v (MkTrie t)     = MkTrie (IntMap.insert k v t)   trieDelete k (MkTrie t)       = MkTrie (IntMap.delete k t)+  trieAlter k f (MkTrie t)      = MkTrie (IntMap.alter f k t)   trieEmpty                     = MkTrie IntMap.empty   trieSingleton k v             = MkTrie (IntMap.singleton k v)   trieNull (MkTrie x)           = IntMap.null x   trieMap f (MkTrie x)          = MkTrie (IntMap.map f x)   trieTraverse f (MkTrie x)     = fmap MkTrie (traverse f x)-  trieShowsPrec p (MkTrie x)    = showsPrec p x   trieMapMaybeWithKey f (MkTrie x)  = MkTrie (IntMap.mapMaybeWithKey f x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,6,4)+    MkTrie <$> IntMap.traverseMaybeWithKey f x+#else+    MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey f x+#endif   trieFoldWithKey f z (MkTrie x)    = IntMap.foldrWithKey f z x   trieTraverseWithKey f (MkTrie x)  = fmap MkTrie (IntMap.traverseWithKey f x)   trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (IntMap.mergeWithKey f (coerce g) (coerce h) x y)@@ -199,29 +244,82 @@   {-# INLINABLE trieInsert #-}   {-# INLINABLE trieLookup #-}   {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}   {-# INLINABLE trieSingleton #-}   {-# INLINABLE trieFoldWithKey #-}-  {-# INLINABLE trieShowsPrec #-}   {-# INLINABLE trieTraverse #-}   {-# INLINABLE trieTraverseWithKey #-}   {-# INLINABLE trieNull #-}   {-# INLINABLE trieMap #-}   {-# INLINABLE trieMergeWithKey #-}   {-# INLINABLE trieMapMaybeWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-} +instance ShowTrieKey Int where+  trieShowsPrec p (MkTrie x)    = showsPrec p x+  {-# INLINABLE trieShowsPrec #-}+ -- | 'Integer' tries are implemented with 'Map'. instance TrieKey Integer where   type TrieRep Integer              = Map Integer   trieLookup k (MkTrie t)           = Map.lookup k t   trieInsert k v (MkTrie t)         = MkTrie (Map.insert k v t)   trieDelete k (MkTrie t)           = MkTrie (Map.delete k t)+  trieAlter k f (MkTrie t)          = MkTrie (Map.alter f k t)   trieEmpty                         = MkTrie Map.empty   trieSingleton k v                 = MkTrie (Map.singleton k v)   trieNull (MkTrie x)               = Map.null x   trieMap f (MkTrie x)              = MkTrie (Map.map f x)   trieTraverse f (MkTrie x)         = fmap MkTrie (traverse f x)+  trieMapMaybeWithKey f (MkTrie x)  = MkTrie (Map.mapMaybeWithKey f x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,5,8)+    MkTrie <$> Map.traverseMaybeWithKey f x+#else+    MkTrie . Map.mapMaybe id <$> Map.traverseWithKey f x+#endif+  trieFoldWithKey f z (MkTrie x)    = Map.foldrWithKey f z x+  trieTraverseWithKey f (MkTrie x)  = fmap MkTrie (Map.traverseWithKey f x)+  trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (Map.mergeWithKey f (coerce g) (coerce h) x y)+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}++instance ShowTrieKey Integer where   trieShowsPrec p (MkTrie x)        = showsPrec p x+  {-# INLINABLE trieShowsPrec #-}++#if MIN_VERSION_base(4,8,0)+-- | 'Natural' tries are implemented with 'Map'.+instance TrieKey Natural where+  type TrieRep Natural              = Map Natural+  trieLookup k (MkTrie t)           = Map.lookup k t+  trieInsert k v (MkTrie t)         = MkTrie (Map.insert k v t)+  trieDelete k (MkTrie t)           = MkTrie (Map.delete k t)+  trieAlter k f (MkTrie t)          = MkTrie (Map.alter f k t)+  trieEmpty                         = MkTrie Map.empty+  trieSingleton k v                 = MkTrie (Map.singleton k v)+  trieNull (MkTrie x)               = Map.null x+  trieMap f (MkTrie x)              = MkTrie (Map.map f x)+  trieTraverse f (MkTrie x)         = fmap MkTrie (traverse f x)   trieMapMaybeWithKey f (MkTrie x)  = MkTrie (Map.mapMaybeWithKey f x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,5,8)+    MkTrie <$> Map.traverseMaybeWithKey f x+#else+    MkTrie . Map.mapMaybe id <$> Map.traverseWithKey f x+#endif   trieFoldWithKey f z (MkTrie x)    = Map.foldrWithKey f z x   trieTraverseWithKey f (MkTrie x)  = fmap MkTrie (Map.traverseWithKey f x)   trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (Map.mergeWithKey f (coerce g) (coerce h) x y)@@ -229,29 +327,83 @@   {-# INLINABLE trieInsert #-}   {-# INLINABLE trieLookup #-}   {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}   {-# INLINABLE trieSingleton #-}   {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}++instance ShowTrieKey Natural where+  trieShowsPrec p (MkTrie x)        = showsPrec p x   {-# INLINABLE trieShowsPrec #-}+#endif++-- | 'Word' tries are implemented with 'IntMap'.+instance TrieKey Word where+  type TrieRep Word                 = IntMap+  trieLookup k (MkTrie t)           = IntMap.lookup (fromIntegral k) t+  trieDelete k (MkTrie t)           = MkTrie (IntMap.delete (fromIntegral k) t)+  trieInsert k v (MkTrie t)         = MkTrie (IntMap.insert (fromIntegral k) v t)+  trieAlter k f (MkTrie t)          = MkTrie (IntMap.alter f (fromIntegral k) t)+  trieEmpty                         = MkTrie IntMap.empty+  trieSingleton k v                 = MkTrie (IntMap.singleton (fromIntegral k) v)+  trieNull (MkTrie x)               = IntMap.null x+  trieMap f (MkTrie x)              = MkTrie (IntMap.map f x)+  trieTraverse f (MkTrie x)         = fmap MkTrie (traverse f x)+  trieMapMaybeWithKey f (MkTrie x)  = MkTrie (IntMap.mapMaybeWithKey (f . fromIntegral) x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,6,4)+    MkTrie <$> IntMap.traverseMaybeWithKey (f . fromIntegral) x+#else+    MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey (f . fromIntegral) x+#endif+  trieFoldWithKey f z (MkTrie x)    = IntMap.foldrWithKey (f . fromIntegral) z x+  trieTraverseWithKey f (MkTrie x)  = fmap MkTrie (IntMap.traverseWithKey (f . fromIntegral) x)+  trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (IntMap.mergeWithKey (f . fromIntegral) (coerce g) (coerce h) x y)+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}   {-# INLINABLE trieTraverse #-}   {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-}   {-# INLINABLE trieNull #-}   {-# INLINABLE trieMap #-}   {-# INLINABLE trieMergeWithKey #-}   {-# INLINABLE trieMapMaybeWithKey #-} +instance ShowTrieKey Word where+  trieShowsPrec p (MkTrie x) =+    showParen (p > 10) (showString "fromList " . shows [(fromIntegral k :: Word, v) | (k,v) <- IntMap.toList x])+  {-# INLINABLE trieShowsPrec #-}+ -- | 'Char' tries are implemented with 'IntMap'. instance TrieKey Char where   type TrieRep Char                 = IntMap   trieLookup k (MkTrie t)           = IntMap.lookup (ord k) t   trieDelete k (MkTrie t)           = MkTrie (IntMap.delete (ord k) t)   trieInsert k v (MkTrie t)         = MkTrie (IntMap.insert (ord k) v t)+  trieAlter k f (MkTrie t)          = MkTrie (IntMap.alter f (ord k) t)   trieEmpty                         = MkTrie IntMap.empty   trieSingleton k v                 = MkTrie (IntMap.singleton (ord k) v)   trieNull (MkTrie x)               = IntMap.null x   trieMap f (MkTrie x)              = MkTrie (IntMap.map f x)   trieTraverse f (MkTrie x)         = fmap MkTrie (traverse f x)-  trieShowsPrec p (MkTrie x)        = showsPrec p x   trieMapMaybeWithKey f (MkTrie x)  = MkTrie (IntMap.mapMaybeWithKey (f . chr) x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,6,4)+    MkTrie <$> IntMap.traverseMaybeWithKey (f . chr) x+#else+    MkTrie . IntMap.mapMaybe id <$> IntMap.traverseWithKey (f . chr) x+#endif   trieFoldWithKey f z (MkTrie x)    = IntMap.foldrWithKey (f . chr) z x   trieTraverseWithKey f (MkTrie x)  = fmap MkTrie (IntMap.traverseWithKey (f . chr) x)   trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (IntMap.mergeWithKey (f . chr) (coerce g) (coerce h) x y)@@ -259,16 +411,21 @@   {-# INLINABLE trieInsert #-}   {-# INLINABLE trieLookup #-}   {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}   {-# INLINABLE trieSingleton #-}   {-# INLINABLE trieFoldWithKey #-}-  {-# INLINABLE trieShowsPrec #-}   {-# INLINABLE trieTraverse #-}   {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-}   {-# INLINABLE trieNull #-}   {-# INLINABLE trieMap #-}   {-# INLINABLE trieMergeWithKey #-}   {-# INLINABLE trieMapMaybeWithKey #-} +instance ShowTrieKey Char where+  trieShowsPrec p (MkTrie x)        = showsPrec p x+  {-# INLINABLE trieShowsPrec #-}+ -- | Tries indexed by 'OrdKey' will be represented as an ordinary 'Map' -- and the keys will be compared based on the 'Ord' instance for @k@. newtype OrdKey k = OrdKey { getOrdKey :: k }@@ -278,18 +435,24 @@ -- intended for cases where it is better for some reason -- to force the use of a 'Map' than to use the generically -- derived structure.-instance (Show k, Ord k) => TrieKey (OrdKey k) where+instance Ord k => TrieKey (OrdKey k) where   type TrieRep (OrdKey k)               = Map k   trieLookup (OrdKey k) (MkTrie x)      = Map.lookup k x   trieInsert (OrdKey k) v (MkTrie x)    = MkTrie (Map.insert k v x)   trieDelete (OrdKey k) (MkTrie x)      = MkTrie (Map.delete k x)+  trieAlter (OrdKey k) f (MkTrie x)     = MkTrie (Map.alter f k x)   trieEmpty                             = MkTrie Map.empty   trieSingleton (OrdKey k) v            = MkTrie (Map.singleton k v)   trieNull (MkTrie x)                   = Map.null x   trieMap f (MkTrie x)                  = MkTrie (Map.map f x)   trieTraverse f (MkTrie x)             = fmap MkTrie (traverse f x)-  trieShowsPrec p (MkTrie x)            = showsPrec p x   trieMapMaybeWithKey f (MkTrie x)      = MkTrie (Map.mapMaybeWithKey (f . OrdKey) x)+  trieTraverseMaybeWithKey f (MkTrie x) =+#if MIN_VERSION_containers (0,5,8)+    MkTrie <$> Map.traverseMaybeWithKey (f . OrdKey) x+#else+    MkTrie . Map.mapMaybe id <$> Map.traverseWithKey (f . OrdKey) x+#endif   trieFoldWithKey f z (MkTrie x)        = Map.foldrWithKey (f . OrdKey) z x   trieTraverseWithKey f (MkTrie x)      = fmap MkTrie (Map.traverseWithKey (f . OrdKey) x)   trieMergeWithKey f g h (MkTrie x) (MkTrie y) = MkTrie (Map.mergeWithKey (f . OrdKey) (coerce g) (coerce h) x y)@@ -297,29 +460,49 @@   {-# INLINABLE trieInsert #-}   {-# INLINABLE trieLookup #-}   {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieAlter #-}   {-# INLINABLE trieSingleton #-}   {-# INLINABLE trieFoldWithKey #-}-  {-# INLINABLE trieShowsPrec #-}   {-# INLINABLE trieTraverse #-}   {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieTraverseMaybeWithKey #-}   {-# INLINABLE trieNull #-}   {-# INLINABLE trieMap #-}   {-# INLINABLE trieMergeWithKey #-}   {-# INLINABLE trieMapMaybeWithKey #-} +instance (Show k, Ord k) => ShowTrieKey (OrdKey k) where+  trieShowsPrec p (MkTrie x)            = showsPrec p x+  {-# INLINABLE trieShowsPrec #-}+ ------------------------------------------------------------------------------ -- Automatically derived instances for common types ------------------------------------------------------------------------------ +#if MIN_VERSION_base(4,8,0)+instance                                      TrieKey Void+instance                                      ShowTrieKey Void+#endif instance                                      TrieKey ()+instance                                      ShowTrieKey () instance                                      TrieKey Bool+instance                                      ShowTrieKey Bool+instance                                      TrieKey Ordering+instance                                      ShowTrieKey Ordering instance TrieKey k                         => TrieKey (Maybe k)+instance ShowTrieKey k                     => ShowTrieKey (Maybe k) instance (TrieKey a, TrieKey b)            => TrieKey (Either a b)+instance (ShowTrieKey a, ShowTrieKey b)    => ShowTrieKey (Either a b) instance (TrieKey a, TrieKey b)            => TrieKey (a,b)+instance (ShowTrieKey a, ShowTrieKey b)    => ShowTrieKey (a,b) instance (TrieKey a, TrieKey b, TrieKey c) => TrieKey (a,b,c)+instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c) => ShowTrieKey (a,b,c) instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d) => TrieKey (a,b,c,d)+instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c, ShowTrieKey d) => ShowTrieKey (a,b,c,d) instance (TrieKey a, TrieKey b, TrieKey c, TrieKey d, TrieKey e) => TrieKey (a,b,c,d,e)+instance (ShowTrieKey a, ShowTrieKey b, ShowTrieKey c, ShowTrieKey d, ShowTrieKey e) => ShowTrieKey (a,b,c,d,e) instance TrieKey k                         => TrieKey [k]+instance ShowTrieKey k                     => ShowTrieKey [k]  ------------------------------------------------------------------------------ -- Generic 'TrieKey' method implementations@@ -380,6 +563,15 @@ genericDelete k m = wrap (gtrieDelete (from k) =<< unwrap m) {-# INLINABLE genericDelete #-} +-- | Generic implementation of 'alter'. This is the default implementation.+genericAlter ::+    ( GTrieKey (Rep k), Generic k+    , TrieRep k ~ TrieRepDefault k+    ) =>+    k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a+genericAlter k f m = wrap (gtrieAlter (from k) f =<< unwrap m)+{-# INLINABLE genericAlter #-}+ -- | Generic implementation of 'trieMap'. This is the default implementation. genericTrieMap ::     ( GTrieKey (Rep k)@@ -444,6 +636,16 @@ genericTraverseWithKey f m = fmap wrap (traverse (gtraverseWithKey (f . to)) (unwrap m)) {-# INLINABLE genericTraverseWithKey #-} +-- | Generic implementation of 'traverseMaybeWithKey'. This is the default implementation.+genericTraverseMaybeWithKey ::+    ( GTrieKey (Rep k), Generic k+    , TrieRep k ~ TrieRepDefault k+    , Applicative f+    ) =>+    (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)+genericTraverseMaybeWithKey f m = fmap (maybe (MkTrie EmptyTrie) wrap) (traverse (gtraverseMaybeWithKey (f . to)) (unwrap m))+{-# INLINABLE genericTraverseMaybeWithKey #-}+ -- | Generic implementation of 'mergeWithKey'. This is the default implementation. genericMergeWithKey ::     ( GTrieKey (Rep k), Generic k@@ -481,7 +683,15 @@ data TrieRepDefault k a = EmptyTrie | NonEmptyTrie !(GTrie (Rep k) a)  -- | Mapping of generic representation of keys to trie structures.+#if __GLASGOW_HASKELL__ >= 810+type GTrie :: (Type -> Type) -> Type -> Type+data    family   GTrie f a+#elif MIN_VERSION_base(4,9,0)+data    family   GTrie (f :: Type -> Type) a+#else data    family   GTrie (f :: * -> *) a+#endif+ newtype instance GTrie (M1 i c f) a     = MTrie (GTrie f a) data    instance GTrie (f :+: g)  a     = STrieL !(GTrie f a)                                         | STrieR !(GTrie g a)@@ -501,11 +711,13 @@   gtrieInsert    :: f p -> a -> GTrie f a -> GTrie f a   gtrieSingleton :: f p -> a -> GTrie f a   gtrieDelete    :: f p -> GTrie f a -> Maybe (GTrie f a)+  gtrieAlter     :: f p -> (Maybe a -> Maybe a) -> GTrie f a -> Maybe (GTrie f a)   gtrieMap       :: (a -> b) -> GTrie f a -> GTrie f b   gtrieTraverse  :: Applicative m => (a -> m b) -> GTrie f a -> m (GTrie f b)   gmapMaybeWithKey :: (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)   gfoldWithKey   :: (f p -> a -> r -> r) -> r -> GTrie f a -> r   gtraverseWithKey :: Applicative m => (f p -> a -> m b) -> GTrie f a -> m (GTrie f b)+  gtraverseMaybeWithKey :: Applicative m => (f p -> a -> m (Maybe b)) -> GTrie f a -> m (Maybe (GTrie f b))   gmergeWithKey  :: (f p -> a -> b -> Maybe c) ->                     (GTrie f a -> Maybe (GTrie f c)) ->                     (GTrie f b -> Maybe (GTrie f c)) ->@@ -527,24 +739,28 @@   gtrieInsert (M1 k) v (MTrie t)= MTrie (gtrieInsert k v t)   gtrieSingleton (M1 k) v       = MTrie (gtrieSingleton k v)   gtrieDelete (M1 k) (MTrie x)  = fmap MTrie (gtrieDelete k x)+  gtrieAlter (M1 k) f (MTrie x) = fmap MTrie (gtrieAlter k f x)   gtrieMap f (MTrie x)          = MTrie (gtrieMap f x)   gtrieTraverse f (MTrie x)     = fmap MTrie (gtrieTraverse f x)   gmapMaybeWithKey f (MTrie x)  = fmap MTrie (gmapMaybeWithKey (f . M1) x)   gfoldWithKey f z (MTrie x)    = gfoldWithKey (f . M1) z x   gtraverseWithKey f (MTrie x)  = fmap MTrie (gtraverseWithKey (f . M1) x)+  gtraverseMaybeWithKey f (MTrie x)  = fmap coerce (gtraverseMaybeWithKey (f . M1) x)   gmergeWithKey f g h (MTrie x) (MTrie y) = fmap MTrie (gmergeWithKey (f . M1) (coerce g) (coerce h) x y)   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieMap #-}   {-# INLINE gmapMaybeWithKey #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}  #if MIN_VERSION_base(4,9,0)-data MProxy (c :: Meta) (f :: * -> *) a = MProxy+data MProxy (c :: Meta) (f :: Type -> Type) a = MProxy #else data MProxy (c :: *)    (f :: * -> *) a = MProxy #endif@@ -575,11 +791,13 @@   gtrieInsert (K1 k) v (KTrie t)        = KTrie (trieInsert k v t)   gtrieSingleton (K1 k) v               = KTrie (trieSingleton k v)   gtrieDelete (K1 k) (KTrie t)          = fmap KTrie (checkNull (trieDelete k t))+  gtrieAlter (K1 k) f (KTrie t)         = fmap KTrie (checkNull (trieAlter k f t))   gtrieMap f (KTrie x)                  = KTrie (trieMap f x)   gtrieTraverse f (KTrie x)             = fmap KTrie (trieTraverse f x)   gmapMaybeWithKey f (KTrie x)          = fmap KTrie (checkNull (trieMapMaybeWithKey (f . K1) x))   gfoldWithKey f z (KTrie x)            = trieFoldWithKey (f . K1) z x   gtraverseWithKey f (KTrie x)          = fmap KTrie (trieTraverseWithKey (f . K1) x)+  gtraverseMaybeWithKey f (KTrie x)     = fmap (fmap KTrie . checkNull) (trieTraverseMaybeWithKey (f . K1) x)   gmergeWithKey f g h (KTrie x) (KTrie y) = fmap KTrie (checkNull (trieMergeWithKey (f . K1) g' h' x y))      where      g' t = case g (KTrie t) of@@ -592,15 +810,17 @@   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieMap #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-} -instance TrieKey k => GTrieKeyShow (K1 i k) where-  gtrieShowsPrec p (KTrie x)            = showsPrec p x+instance ShowTrieKey k => GTrieKeyShow (K1 i k) where+  gtrieShowsPrec p (KTrie x)            = trieShowsPrec p x  ------------------------------------------------------------------------------ -- Generic implementation for products@@ -610,14 +830,35 @@ instance (GTrieKey f, GTrieKey g) => GTrieKey (f :*: g) where    gtrieLookup (i :*: j) (PTrie x)       = gtrieLookup j =<< gtrieLookup i x-  gtrieInsert (i :*: j) v (PTrie t)     = case gtrieLookup i t of-                                            Nothing -> PTrie (gtrieInsert i (gtrieSingleton j v) t)-                                            Just ti -> PTrie (gtrieInsert i (gtrieInsert j v ti) t)-  gtrieDelete (i :*: j) (PTrie t)       = case gtrieLookup i t of-                                            Nothing -> Just (PTrie t)-                                            Just ti -> case gtrieDelete j ti of-                                                         Nothing -> fmap PTrie $! gtrieDelete i t-                                                         Just tj -> Just $! PTrie (gtrieInsert i tj t)+  gtrieInsert (i :*: j) v (PTrie t)     = case gtrieAlter i f t of+  -- The "impossible" error is unfortunate. We *could* add another function+  --+  --   ginsertChange :: f i -> (Maybe a -> a) -> GTrie i a -> GTrie i a+  --+  -- and use that, but that would only push the "impossible" errors to the+  -- implementations using `Map` and `IntMap`, which doesn't seem to help.+                                            Nothing -> error "gtrieInsert: insertion produced an empty trie"+                                            Just t' -> PTrie t'+    where+      -- f :: Maybe (GTrie g a) -> Maybe (GTrie g a)+      f Nothing = Just $! gtrieSingleton j v+      f (Just u) = Just $! gtrieInsert j v u++  gtrieDelete (i :*: j) (PTrie t)       = fmap PTrie (gtrieAlter i f t)+    where+      -- f :: Maybe (GTrie g a) -> Maybe (GTrie g a)+      f Nothing = Nothing+      f (Just u) = gtrieDelete j u++  gtrieAlter (i :*: j) f (PTrie t)      = fmap PTrie (gtrieAlter i g t)+    where+      -- g :: Maybe (GTrie g a) -> Maybe (GTrie g a)+      g Nothing =+        case f Nothing of+          Nothing -> Nothing+          Just v -> Just $! gtrieSingleton j v+      g (Just u) = gtrieAlter j f u+   gtrieSingleton (i :*: j) v            = PTrie (gtrieSingleton i (gtrieSingleton j v))   gtrieMap f (PTrie x)                  = PTrie (gtrieMap (gtrieMap f) x)   gtrieTraverse f (PTrie x)             = fmap PTrie (gtrieTraverse (gtrieTraverse f) x)@@ -625,6 +866,8 @@   gfoldWithKey f z (PTrie x)            = gfoldWithKey (\i m r -> gfoldWithKey (\j -> f (i:*:j)) r m) z x   gtraverseWithKey f (PTrie x)          = fmap PTrie (gtraverseWithKey (\i ->                                                       gtraverseWithKey (\j -> f (i :*: j))) x)+  gtraverseMaybeWithKey f (PTrie x)     = fmap (fmap PTrie) (gtraverseMaybeWithKey (\i ->+                                                      gtraverseMaybeWithKey (\j -> f (i :*: j))) x)   gmergeWithKey f g h (PTrie x) (PTrie y) =     fmap PTrie $!        gmergeWithKey@@ -646,11 +889,13 @@   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieMap #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-} @@ -692,6 +937,25 @@                                             Nothing -> Just $! STrieL x                                             Just y' -> Just $! STrieB x y' +  gtrieAlter (L1 k) f (STrieL x)        = do+                                            x' <- gtrieAlter k f x+                                            Just $! STrieL x'+  gtrieAlter (L1 k) f t@(STrieR y)      = case f Nothing of+                                            Nothing -> Just t+                                            Just v -> Just $! STrieB (gtrieSingleton k v) y+  gtrieAlter (L1 k) f (STrieB x y)      = case gtrieAlter k f x of+                                            Just x' -> Just $! STrieB x' y+                                            Nothing -> Just $! STrieR y+  gtrieAlter (R1 k) f (STrieR y)        = do+                                            y' <- gtrieAlter k f y+                                            Just $! STrieR y'+  gtrieAlter (R1 k) f t@(STrieL x)      = case f Nothing of+                                            Nothing -> Just t+                                            Just v -> Just $! STrieB x (gtrieSingleton k v)+  gtrieAlter (R1 k) f (STrieB x y)      = case gtrieAlter k f y of+                                            Just y' -> Just $! STrieB x y'+                                            Nothing -> Just $! STrieL x+   gtrieMap f (STrieB x y)               = STrieB (gtrieMap f x) (gtrieMap f y)   gtrieMap f (STrieL x)                 = STrieL (gtrieMap f x)   gtrieMap f (STrieR y)                 = STrieR (gtrieMap f y)@@ -708,6 +972,16 @@                                             (Nothing, Just y') -> Just $! STrieR y'                                             (Just x', Just y') -> Just $! STrieB x' y' +  gtraverseMaybeWithKey f (STrieL x)         = fmap STrieL <$> gtraverseMaybeWithKey (f . L1) x+  gtraverseMaybeWithKey f (STrieR y)         = fmap STrieR <$> gtraverseMaybeWithKey (f . R1) y+  gtraverseMaybeWithKey f (STrieB x y)       =+    liftA2 finish (gtraverseMaybeWithKey (f . L1) x) (gtraverseMaybeWithKey (f . R1) y)+    where+      finish Nothing   Nothing    = Nothing+      finish (Just x') Nothing    = Just $! STrieL x'+      finish Nothing   (Just y')  = Just $! STrieR y'+      finish (Just x') (Just y')  = Just $! STrieB x' y'+   gfoldWithKey f z (STrieL x)           = gfoldWithKey (f . L1) z x   gfoldWithKey f z (STrieR y)           = gfoldWithKey (f . R1) z y   gfoldWithKey f z (STrieB x y)         = gfoldWithKey (f . L1) (gfoldWithKey (f . R1) z y) x@@ -752,11 +1026,13 @@   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gtrieMap #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-} @@ -782,21 +1058,27 @@   gtrieLookup _ (UTrie x)       = Just x   gtrieInsert _ v _             = UTrie v   gtrieDelete _ _               = Nothing+  gtrieAlter _ f (UTrie x)      = case f (Just x) of+                                    Nothing -> Nothing+                                    Just x' -> Just $! UTrie x'   gtrieSingleton _              = UTrie   gtrieMap f (UTrie x)          = UTrie (f x)   gtrieTraverse f (UTrie x)     = fmap UTrie (f x)   gmapMaybeWithKey f (UTrie x)  = fmap UTrie $! f U1 x+  gtraverseMaybeWithKey f (UTrie x)  = fmap (fmap UTrie) $! f U1 x   gfoldWithKey f z (UTrie x)    = f U1 x z   gtraverseWithKey f (UTrie x)  = fmap UTrie (f U1 x)   gmergeWithKey f _ _ (UTrie x) (UTrie y) = fmap UTrie $! f U1 x y   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gtrieMap #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-} @@ -807,26 +1089,43 @@ -- Generic implementation for empty types ------------------------------------------------------------------------------ --- | Tries of types without constructors are represented by a unit.+-- | Tries of types without constructors are represented by an empty type. instance GTrieKey V1 where-  gtrieLookup k t               = k `seq` t `seq` error "GTrieKey.V1: gtrieLookup"-  gtrieInsert k _ t             = k `seq` t `seq` error "GTrieKey.V1: gtrieInsert"-  gtrieDelete k t               = k `seq` t `seq` error "GTrieKey.V1: gtrieDelete"-  gtrieSingleton k _            = k `seq` error "GTrieKey.V1: gtrieSingleton"-  gtrieMap _ t                  = t `seq` error "GTrieKey.V1: gtrieMap"-  gtrieTraverse _ t             = t `seq` error "GTrieKey.V1: gtrieTraverse"-  gmapMaybeWithKey _ t          = t `seq` error "GTrieKey.V1: gmapMaybeWithKey"-  gfoldWithKey _ _ t            = t `seq` error "GTrieKey.V1: gmapFoldWithKey"-  gtraverseWithKey _ t          = t `seq` error "GTrieKey.V1: gtraverseWithKey"-  gmergeWithKey _ _ _ t u       = t `seq` u `seq` error "GTrieKey.V1: gmergeWithKey"+-- Why is this represented by an empty type? One might expect it would+-- be represented by a unit type, as there is exactly one total function+-- from any empty type to any other type. First, remember that+-- TrieRepDefault offers an EmptyTrie constructor. So a TrieMap Void x+-- will be represented by that. Next, note that while the generic Rep+-- types can be put together in arbitrary ways, derived Generic instances (which+-- are the only ones that matter) are always structured as sums of products,+-- and only use V1 at the outermost level. That is, V1 will only appear in a+-- generic representation if it is the only thing there (aside from M1+-- wrappers). In particular, the only GTrie types that contain V1 are ones+-- for empty types, which are adequately represented by EmptyTrie. Indeed,+-- if we offered an inhabited GTrie for a Void type, we'd run into trouble,+-- because then we'd falsely claim that the TrieMap from Void isn't null!+  gtrieLookup _ t               = case t of+  gtrieInsert _ _ t             = case t of+  gtrieDelete _ t               = case t of+  gtrieAlter _ _ t              = case t of+  gtrieSingleton k _            = case k of+  gtrieMap _ t                  = case t of+  gtrieTraverse _ t             = case t of+  gmapMaybeWithKey _ t          = case t of+  gfoldWithKey _ _ t            = case t of+  gtraverseWithKey _ t          = case t of+  gtraverseMaybeWithKey _ t     = case t of+  gmergeWithKey _ _ _ t _       = case t of   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}+  {-# INLINE gtrieAlter #-}   {-# INLINE gtrieSingleton #-}   {-# INLINE gtrieMap #-}   {-# INLINE gtrieTraverse #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}+  {-# INLINE gtraverseMaybeWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-} @@ -838,8 +1137,9 @@ -- Various instances for Trie ------------------------------------------------------------------------------ -instance (Show a, TrieKey  k) => Show (Trie  k a) where-  showsPrec = trieShowsPrec+instance (TrieKey k, Show k, Show a) => Show (Trie k a) where+  showsPrec d m  = showParen (d > 10) $+    showString "fromList " . shows (toList m)  instance (Show a, GTrieKeyShow f) => Show (GTrie f a) where   showsPrec = gtrieShowsPrec@@ -847,8 +1147,12 @@ instance TrieKey k => Functor (Trie k) where   fmap = trieMap -instance TrieKey k => Foldable (Trie k) where+instance TrieKey k => Foldable.Foldable (Trie k) where+  foldMap = Traversable.foldMapDefault   foldr f = trieFoldWithKey (\_ -> f)+#if MIN_VERSION_base(4,8,0)+  null = trieNull+#endif  instance TrieKey k => Traversable (Trie k) where   traverse = trieTraverse

@@ -0,0 +1,37 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE PackageImports #-}+-- | This hideous module lets us avoid dealing with the fact that+-- various functions haven't always been exported from the standard+-- Prelude.+module Prelude+  ( module Prel+#if !MIN_VERSION_base(4,18,0)+  , Applicative (..)+#endif+#if !MIN_VERSION_base(4,10,0)+  , liftA2+#endif+#if !MIN_VERSION_base(4,8,0)+  , Foldable (foldMap)+  , Traversable (traverse)+  , Word+  , (<$>)+#endif+  )+  where++import "base" Prelude as Prel+#if !MIN_VERSION_base(4,18,0)+import Control.Applicative (Applicative (..))+#endif++#if !MIN_VERSION_base(4,10,0)+import Control.Applicative (liftA2)+#endif++#if !MIN_VERSION_base(4,8,0)+import Data.Foldable (Foldable (..))+import Data.Traversable (Traversable (..))+import Data.Word (Word)+import Control.Applicative ((<$>))+#endif