generic-trie 0.3.0.1 → 0.3.0.2

raw patch · 4 files changed

+78/−122 lines, 4 filesdep ~basedep ~transformersPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base, transformers

API changes (from Hackage documentation)

Files

• CHANGELOG.md +3/−0
• generic-trie.cabal +6/−3
• src/Data/GenericTrie.hs +7/−3
• src/Data/GenericTrie/Internal.hs +62/−116

@@ -0,0 +1,3 @@+0.3.0.2+-------+* GHC 8 compatibility

@@ -1,5 +1,5 @@ name:                generic-trie-version:             0.3.0.1+version:             0.3.0.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@@ -19,11 +19,14 @@ homepage:            http://github.com/glguy/tries bug-reports:         http://github.com/glguy/tries/issues +extra-source-files:+  CHANGELOG.md+ library   exposed-modules:     Data.GenericTrie,                        Data.GenericTrie.Internal-  build-depends:       base             >= 4.5     && < 4.9,-                       transformers     >= 0.2     && < 0.5,+  build-depends:       base             >= 4.5     && < 4.10,+                       transformers     >= 0.2     && < 0.6,                        containers       >= 0.4.2.1 && < 0.6   GHC-options:         -O2 -Wall 

@@ -46,7 +46,7 @@   , insertWith   , insertWith'   , delete-  , at +  , at    -- ** Queries   , member@@ -124,8 +124,12 @@  -- | Lens for the value at a given key at :: (Functor f, TrieKey k) => k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)-at = trieAt-{-# INLINE at #-}+at k f m = fmap aux (f mv)+  where+  mv = lookup k m+  aux r = case r of+    Nothing -> maybe m (const (delete k m)) mv+    Just v' -> insert k v' m  -- | Insert an element into a trie insert :: TrieKey k => k -> a -> Trie k a -> Trie k a

@@ -6,7 +6,12 @@ {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE Trustworthy #-} -- coerce+{-# LANGUAGE CPP #-} -- MProxy on ghc >= 8 +#if MIN_VERSION_base(4,9,0)+{-# LANGUAGE DataKinds #-} -- Meta+#endif+ -- | Unstable implementation details module Data.GenericTrie.Internal   ( TrieKey(..)@@ -23,7 +28,6 @@   , genericMapMaybeWithKey   , genericSingleton   , genericEmpty-  , genericAt   , genericFoldWithKey   , genericTraverseWithKey   , TrieRepDefault@@ -70,9 +74,6 @@   -- | Delete element from trie   trieDelete :: k -> Trie k a -> Trie k a -  trieAt :: Functor f => k -> (Maybe a -> f (Maybe a)) ->-                              Trie k a -> f (Trie k a)-   -- | Construct a trie holding a single value   trieSingleton :: k -> a -> Trie k a @@ -171,11 +172,6 @@     Trie k a -> Trie k b -> Trie k c   trieMergeWithKey = genericMergeWithKey -  default trieAt ::-    ( GTrieKey (Rep k) , TrieRep k ~ TrieRepDefault k, Generic k, Functor f ) =>-    k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)-  trieAt = genericAt- -- | The default implementation of a 'TrieRep' is 'GTrie' wrapped in -- a 'Maybe'. This wrapping is due to the 'GTrie' being a non-empty -- trie allowing all the of the "emptiness" to be represented at the@@ -190,15 +186,6 @@ -- Manually derived instances for base types ------------------------------------------------------------------------------ -simpleAt ::-  (Functor f, TrieKey k) =>-  k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)-simpleAt k f m = flip fmap (f mv) $ \r -> case r of-    Nothing -> maybe m (const (trieDelete k m)) mv-    Just v' -> trieInsert k v' m-    where mv = trieLookup k m-{-# INLINE simpleAt #-}- -- | 'Int' tries are implemented with 'IntMap'. instance TrieKey Int where   type TrieRep Int              = IntMap@@ -215,20 +202,19 @@   trieFoldWithKey f z (MkTrie x)    = IntMap.foldWithKey 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)-  trieAt                        = simpleAt-  {-# INLINE trieEmpty #-}-  {-# INLINE trieInsert #-}-  {-# INLINE trieLookup #-}-  {-# INLINE trieDelete #-}-  {-# INLINE trieSingleton #-}-  {-# INLINE trieFoldWithKey #-}-  {-# INLINE trieShowsPrec #-}-  {-# INLINE trieTraverse #-}-  {-# INLINE trieTraverseWithKey #-}-  {-# INLINE trieNull #-}-  {-# INLINE trieMap #-}-  {-# INLINE trieMergeWithKey #-}-  {-# INLINE trieMapMaybeWithKey #-}+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieShowsPrec #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}  -- | 'Integer' tries are implemented with 'Map'. instance TrieKey Integer where@@ -246,20 +232,19 @@   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)-  trieAt                            = simpleAt-  {-# INLINE trieEmpty #-}-  {-# INLINE trieInsert #-}-  {-# INLINE trieLookup #-}-  {-# INLINE trieDelete #-}-  {-# INLINE trieSingleton #-}-  {-# INLINE trieFoldWithKey #-}-  {-# INLINE trieShowsPrec #-}-  {-# INLINE trieTraverse #-}-  {-# INLINE trieTraverseWithKey #-}-  {-# INLINE trieNull #-}-  {-# INLINE trieMap #-}-  {-# INLINE trieMergeWithKey #-}-  {-# INLINE trieMapMaybeWithKey #-}+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieShowsPrec #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}  -- | 'Char' tries are implemented with 'IntMap'. instance TrieKey Char where@@ -277,20 +262,19 @@   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)-  trieAt                            = simpleAt-  {-# INLINE trieEmpty #-}-  {-# INLINE trieInsert #-}-  {-# INLINE trieLookup #-}-  {-# INLINE trieDelete #-}-  {-# INLINE trieSingleton #-}-  {-# INLINE trieFoldWithKey #-}-  {-# INLINE trieShowsPrec #-}-  {-# INLINE trieTraverse #-}-  {-# INLINE trieTraverseWithKey #-}-  {-# INLINE trieNull #-}-  {-# INLINE trieMap #-}-  {-# INLINE trieMergeWithKey #-}-  {-# INLINE trieMapMaybeWithKey #-}+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieShowsPrec #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}  -- | Tries indexed by 'OrdKey' will be represented as an ordinary 'Map' -- and the keys will be compared based on the 'Ord' instance for @k@.@@ -316,20 +300,19 @@   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)-  trieAt                                = simpleAt-  {-# INLINE trieEmpty #-}-  {-# INLINE trieInsert #-}-  {-# INLINE trieLookup #-}-  {-# INLINE trieDelete #-}-  {-# INLINE trieSingleton #-}-  {-# INLINE trieFoldWithKey #-}-  {-# INLINE trieShowsPrec #-}-  {-# INLINE trieTraverse #-}-  {-# INLINE trieTraverseWithKey #-}-  {-# INLINE trieNull #-}-  {-# INLINE trieMap #-}-  {-# INLINE trieMergeWithKey #-}-  {-# INLINE trieMapMaybeWithKey #-}+  {-# INLINABLE trieEmpty #-}+  {-# INLINABLE trieInsert #-}+  {-# INLINABLE trieLookup #-}+  {-# INLINABLE trieDelete #-}+  {-# INLINABLE trieSingleton #-}+  {-# INLINABLE trieFoldWithKey #-}+  {-# INLINABLE trieShowsPrec #-}+  {-# INLINABLE trieTraverse #-}+  {-# INLINABLE trieTraverseWithKey #-}+  {-# INLINABLE trieNull #-}+  {-# INLINABLE trieMap #-}+  {-# INLINABLE trieMergeWithKey #-}+  {-# INLINABLE trieMapMaybeWithKey #-}  ------------------------------------------------------------------------------ -- Automatically derived instances for common types@@ -384,19 +367,6 @@ {-# INLINABLE genericEmpty #-}  -- | Generic implementation of 'insert'. This is the default implementation.-genericAt ::-    ( GTrieKey (Rep k), Generic k-    , TrieRep k ~ TrieRepDefault k-    , Functor f-    ) =>-    k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)-genericAt k f (MkTrie (Compose m)) =-  case m of-    Nothing -> fmap (MkTrie . Compose . fmap (gtrieSingleton (from k))) (f Nothing)-    Just t  -> gtrieAt (MkTrie . Compose) (from k) f t-{-# INLINABLE genericAt #-}---- | Generic implementation of 'insert'. This is the default implementation. genericInsert ::     ( GTrieKey (Rep k), Generic k     , TrieRep k ~ TrieRepDefault k@@ -533,11 +503,6 @@                     (GTrie f a -> Maybe (GTrie f c)) ->                     (GTrie f b -> Maybe (GTrie f c)) ->                     GTrie f a -> GTrie f b -> Maybe (GTrie f c)-  gtrieAt        :: Functor m =>-                      (Maybe (GTrie f a) -> r) ->-                      f p ->-                      (Maybe a -> m (Maybe a)) ->-                      GTrie f a -> m r  -- | The 'GTrieKeyShow' class provides generic implementations -- of 'showsPrec'. This class is separate due to its implementation@@ -561,7 +526,6 @@   gfoldWithKey f z (MTrie x)    = gfoldWithKey (f . M1) z x   gtraverseWithKey f (MTrie x)  = fmap MTrie (gtraverseWithKey (f . M1) x)   gmergeWithKey f g h (MTrie x) (MTrie y) = fmap MTrie (gmergeWithKey (f . M1) (coerce g) (coerce h) x y)-  gtrieAt z (M1 k) f (MTrie x)  = gtrieAt (z . fmap MTrie) k f x   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieSingleton #-}@@ -571,9 +535,12 @@   {-# INLINE gtrieTraverse #-}   {-# INLINE gfoldWithKey #-}   {-# INLINE gtraverseWithKey #-}-  {-# INLINE gtrieAt #-} -data MProxy c (f :: * -> *) a = MProxy+#if MIN_VERSION_base(4,9,0)+data MProxy (c :: Meta) (f :: * -> *) a = MProxy+#else+data MProxy (c :: *)    (f :: * -> *) a = MProxy+#endif  instance GTrieKeyShow f => GTrieKeyShow (M1 D d f) where   gtrieShowsPrec p (MTrie x)    = showsPrec p x@@ -614,7 +581,6 @@      h' t = case h (KTrie t) of               Just (KTrie t') -> t'               Nothing         -> trieEmpty-  gtrieAt z (K1 k) f (KTrie x) = fmap (z . fmap KTrie . checkNull) (trieAt k f x)   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieSingleton #-}@@ -625,7 +591,6 @@   {-# INLINE gtraverseWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-}-  {-# INLINE gtrieAt #-}  instance TrieKey k => GTrieKeyShow (K1 i k) where   gtrieShowsPrec p (KTrie x)            = showsPrec p x@@ -672,12 +637,6 @@     h' i t = do PTrie t' <- h (PTrie (gtrieSingleton i t))                 gtrieLookup i t' -  gtrieAt z (i :*: j) f (PTrie t) = gtrieAt (z . fmap PTrie) i f1 t-    where-    f1 Nothing = fmap (fmap (gtrieSingleton j)) (f Nothing)-    f1 (Just ti) = gtrieAt id j f ti--   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}@@ -688,7 +647,6 @@   {-# INLINE gtraverseWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-}-  {-# INLINE gtrieAt #-}  instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :*: g) where   gtrieShowsPrec p (PTrie x)            = showsPrec p x@@ -785,13 +743,6 @@     hr t = do STrieR t' <- h (STrieR t)               return t' -  gtrieAt z (L1 k) f (STrieL x)   = gtrieAt (z . fmap STrieL) k f x-  gtrieAt z (R1 k) f (STrieR y)   = gtrieAt (z . fmap STrieR) k f y-  gtrieAt z (L1 k) f (STrieR y)   = fmap (z . Just . maybe (STrieR y) (\v -> STrieB (gtrieSingleton k v) y)) (f Nothing)-  gtrieAt z (R1 k) f (STrieL x)   = fmap (z . Just . maybe (STrieL x) (\v -> STrieB x (gtrieSingleton k v))) (f Nothing)-  gtrieAt z (L1 k) f (STrieB x y) = gtrieAt (z . Just . maybe (STrieR y) (`STrieB` y)) k f x-  gtrieAt z (R1 k) f (STrieB x y) = gtrieAt (z . Just . maybe (STrieL x) (x `STrieB`)) k f y-   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}@@ -802,7 +753,6 @@   {-# INLINE gtraverseWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-}-  {-# INLINE gtrieAt #-}  instance (GTrieKeyShow f, GTrieKeyShow g) => GTrieKeyShow (f :+: g) where   gtrieShowsPrec p (STrieB x y)         = showParen (p > 10)@@ -833,7 +783,6 @@   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)-  gtrieAt z _ f (UTrie x)       = fmap (z . fmap UTrie) (f (Just x))   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}@@ -844,7 +793,6 @@   {-# INLINE gtraverseWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-}-  {-# INLINE gtrieAt #-}  instance GTrieKeyShow U1 where   gtrieShowsPrec p (UTrie x)    = showsPrec p x@@ -865,7 +813,6 @@   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"-  gtrieAt _ k _ t               = k `seq` t `seq` error "GTrieKey.V1: gtrieAt"   {-# INLINE gtrieLookup #-}   {-# INLINE gtrieInsert #-}   {-# INLINE gtrieDelete #-}@@ -876,7 +823,6 @@   {-# INLINE gtraverseWithKey #-}   {-# INLINE gmergeWithKey #-}   {-# INLINE gmapMaybeWithKey #-}-  {-# INLINE gtrieAt #-}  instance GTrieKeyShow V1 where   gtrieShowsPrec _ _            = showString "()"