list-tries 0.4.3 → 0.6.7.1
raw patch · 20 files changed
Files
- CHANGELOG.md +113/−0
- CHANGELOG.txt +0/−55
- CREDITS.txt +4/−3
- Data/ListTrie/Base.hs +39/−8
- Data/ListTrie/Base/Classes.hs +0/−1
- Data/ListTrie/Base/Map.hs +41/−40
- Data/ListTrie/Map.hs +28/−10
- Data/ListTrie/Patricia/Base.hs +55/−10
- Data/ListTrie/Patricia/Map.hs +28/−10
- Data/ListTrie/Patricia/Set.hs +28/−8
- Data/ListTrie/Set.hs +28/−8
- LICENSE.txt +1/−1
- README.md +9/−0
- Setup.hs +0/−2
- headers/exports.h +131/−129
- list-tries.cabal +53/−57
- tests/Tests/Cases.hs +1/−3
- tests/Tests/Properties.hs +31/−2
- tests/Tests/Strictness.hs +0/−7
- tests/Tests/TH.hs +9/−1
+ CHANGELOG.md view
@@ -0,0 +1,113 @@+# list-tries-0.6.7.1 (2024-09-04)+* Make tests compile with GHC >= 9.0.+* Drop support for GHC < 8.10.++# list-tries-0.6.7 (2020-05-12)+* Updated dependencies and code for GHC 8.8 and 8.10.++# list-tries-0.6.6 (2018-11-20)+* Updated dependencies and code for GHC 8.6.1, thanks as usual to Mikhail+ Glushenkov.++# list-tries-0.6.5 (2018-03-20)+* Updated dependencies and code for GHC 8.4.1 and QuickCheck-2.11,+ thanks again to Mikhail Glushenkov.++# list-tries-0.6.4 (2017-05-27)+* Updated dependencies for GHC 8.2.1 (release candidate 2) and+ binary-0.9, thanks to Mikhail Glushenkov for helping with this.+* Also a code change due to a newly problematic type inference.++# list-tries-0.6.3 (2016-07-18)+* Dependency update to allow dlist-0.8.++# list-tries-0.6.2 (2016-06-28)+* Updated dependencies for GHC 8.0.1.+* Added Semigroup instances, bringing in a new dependency on semigroups+ on pre-8.0 GHC versions.++# list-tries-0.6.1 (2015-04-03)+* Fixed build on base < 4.8.++# list-tries-0.6.0 (2015-03-28)+* Updated dependencies for GHC 7.10.+* Fixed library vs. test executable dlist dependency mismatch.+* Renamed `Map.toList` to `toListKV` to avoid conflicts with the new+ `Foldable` class. Also renamed `Map.fromList` and `Map.fromListWith`+ to `fromListKV` and `fromListKVWith` to match. Thanks to davean for+ the patch.+* Added Cabal source-repository metadata, pointing to GitHub.++# list-tries-0.5.2 (2014-03-20)+* Updated dependencies, for GHC 7.8 and other new packages.++# list-tries-0.5.1 (2013-05-10)+* Fix cabal build.+* Minor documentation clarification.+* Update `binary` dependency.++# list-tries-0.5 (2013-05-09)+* Added the `lookupPrefix` and `deleteSuffixes` functions, of which especially+ the former was an embarrassing omission:++ lookupPrefix :: [k] -> trie map k a -> trie map k a+ deleteSuffixes :: [k] -> trie map k a -> trie map k a++* Fixed the documentation headers to refer to 's' instead of 'k' as what we+ use for the length of the given key.+* Fixed documentation of 'deletePrefix': its complexity is O(s), not O(m).+* Some dependency updates.++# list-tries-0.4.3 (2012-10-18)+* Dependency updates for GHC 7.6 and otherwise.++# list-tries-0.4.2 (2012-05-23)+* Dependency updates for GHC 7.4, thanks to Anders Kaseorg.++# list-tries-0.4.1 (2011-03-17)+* Dependency update and Cabalization of the test executable, thanks to JP+ Moresmau.++# list-tries-0.4 (2010-09-11)+* Fixed documentation of the `deletePrefix` function: if the given key is not+ a prefix of any key, an empty, not unchanged, map/set is returned. Thanks to+ Brian Bloniarz for the bug report.+* Fixed bug in the Patricia version of `deletePrefix` causing it to not delete+ anything if the prefix to be deleted was a proper prefix of the common+ prefix.+* Changed `children` to return the map as-is instead of converting it into a+ list first:++ children :: Trie trie st map k => trie map k a -> CMap trie map k a++* Added the `children1` function as a single-level equivalent of `children`,+ more directly reflecting the structure of the non-Patricia tries. Requested+ by Brian Bloniarz.++ children1 :: Trie trie st map k => trie map k a -> CMap trie map k a++# list-tries-0.3 (2010-09-09)+* Fixed strictness of the strict versions of the following+ non-Patricia functions: `insert`, `adjust`, `alter`, `union`,+ `difference`, `intersection`, `mapInKeys`; as well as the Patricia+ versions of `insert` and `adjust`. Thanks to Brian Bloniarz for the+ bug report.+* Applied the static argument transformation throughout, improving+ performance.+* Dropped support for containers < 0.3; GHC 6.12 has been out long+ enough, and support for older versions is too crippled to make it+ worthwhile.++# list-tries-0.2 (2010-04-06)+* Dependency update, nothing more.++# list-tries-0.1 (2009-07-05)+* All tries are now instances of `Binary`, thanks to Gregory Crosswhite. Adds a+ dependency on the `binary` library as well as the following two methods to+ the `Map` class in `Base.Map`:++ serializeToList :: m k a -> [(k,a)]+ deserializeFromList :: [(k,a)] -> m k a++# list-tries-0.0 (2009-04-21)+* Initial release.
− CHANGELOG.txt
@@ -1,55 +0,0 @@-2012-10-18, 0.4.3:- Dependency updates for GHC 7.6 and otherwise.--2012-05-23, 0.4.2:- Dependency updates for GHC 7.4, thanks to Anders Kaseorg.--2011-03-17, 0.4.1:- Dependency update and Cabalization of the test executable, thanks to JP- Moresmau.--2010-09-11, 0.4:- Fixed documentation of the 'deletePrefix' function: if the given key is not- a prefix of any key, an empty, not unchanged, map/set is returned. Thanks to- Brian Bloniarz for the bug report.-- Fixed bug in the Patricia version of 'deletePrefix' causing it to not delete- anything if the prefix to be deleted was a proper prefix of the common- prefix.-- Changed 'children' to return the map as-is instead of converting it into a- list first:-- children :: Trie trie st map k => trie map k a -> CMap trie map k a-- Added the 'children1' function as a single-level equivalent of 'children',- more directly reflecting the structure of the non-Patricia tries. Requested- by Brian Bloniarz.-- children1 :: Trie trie st map k => trie map k a -> CMap trie map k a--2010-09-09, 0.3:- Fixed strictness of the strict versions of the following non-Patricia- functions: insert, adjust, alter, union, difference, intersection,- mapInKeys; as well as the Patricia versions of insert and adjust. Thanks to- Brian Bloniarz for the bug report.-- Applied the static argument transformation throughout, improving- performance.-- Dropped support for containers < 0.3; GHC 6.12 has been out long enough, and- support for older versions is too crippled to make it worthwhile.--2010-04-06, 0.2:- Dependency update, nothing more.--2009-07-05, 0.1:- All tries are now instances of Binary, thanks to Gregory Crosswhite. Adds a- dependency on the 'binary' library as well as the following two methods to- the Map class in Base.Map:-- serializeToList :: m k a -> [(k,a)]- deserializeFromList :: [(k,a)] -> m k a--2009-04-21, 0.0:- Initial release.
CREDITS.txt view
@@ -1,4 +1,5 @@-In alphabetical order by surname:-+davean Gregory Crosswhite-Matti Niemenmaa+Mikhail Glushenkov+Matti Niemenmaa+Andrzej Rybczak
Data/ListTrie/Base.hs view
@@ -25,11 +25,11 @@ , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey' , findMin, findMax, deleteMin, deleteMax, minView, maxView , findPredecessor, findSuccessor- , addPrefix, splitPrefix, deletePrefix, children, children1+ , lookupPrefix, addPrefix, deletePrefix, deleteSuffixes+ , splitPrefix, children, children1 , showTrieWith ) where -import Control.Applicative (Applicative(..), (<$>)) import Control.Arrow ((***), first) import qualified Data.DList as DL import Data.DList (DList)@@ -559,7 +559,7 @@ genericMapInKeysWith ($$) unionW j f = go where go tr = mapMap ($$) tr $- Map.fromListWith (unionW j) . map (f *** go) . Map.toList+ Map.fromListKVWith (unionW j) . map (f *** go) . Map.toListKV -- * Folding @@ -612,7 +612,7 @@ -- O(n m) toList :: (Boolable (st a), Trie trie st map k) => trie map k a -> [([k],a)]-toList = genericToList Map.toList DL.cons+toList = genericToList Map.toListKV DL.cons -- O(n m) toAscList :: (Boolable (st a), Trie trie st map k, OrdMap map k)@@ -781,11 +781,14 @@ Just (best,btr) -> fmap (first (best:)) (findMax btr) -- O(m)-findSuccessor :: (Boolable (st a), Trie trie st map k, OrdMap map k)+findSuccessor :: forall trie map st k a .+ (Boolable (st a), Trie trie st map k, OrdMap map k) => [k] -> trie map k a -> Maybe ([k], a) findSuccessor _ tr | null tr = Nothing findSuccessor xs_ tr_ = go xs_ tr_ where+ go :: (Boolable (st a), Trie trie st map k, OrdMap map k)+ => [k] -> trie map k a -> Maybe ([k], a) go [] tr = do (k,t) <- fst . Map.minViewWithKey . tMap $ tr fmap (first (k:)) (findMin t) @@ -799,12 +802,24 @@ -- * Trie-only operations -- O(s)+lookupPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)+ => [k] -> trie map k a -> trie map k a+lookupPrefix [] tr = tr+lookupPrefix (x:xs) tr =+ case Map.lookup x (tMap tr) of+ Nothing -> empty+ Just tr' -> let tr'' = lookupPrefix xs tr'+ in if null tr''+ then tr''+ else mkTrie altEmpty (Map.singleton x tr'')++-- O(s) addPrefix :: (Alt st a, Trie trie st map k) => [k] -> trie map k a -> trie map k a addPrefix [] = id addPrefix (x:xs) = mkTrie altEmpty . Map.singleton x . addPrefix xs --- O(m)+-- O(s) deletePrefix :: (Alt st a, Trie trie st map k) => [k] -> trie map k a -> trie map k a deletePrefix [] tr = tr@@ -813,11 +828,27 @@ Nothing -> empty Just tr' -> deletePrefix xs tr' +-- O(s)+deleteSuffixes :: (Alt st a, Boolable (st a), Trie trie st map k)+ => [k] -> trie map k a -> trie map k a+deleteSuffixes [] _ = empty+deleteSuffixes (x:xs) tr =+ let (v,m) = tParts tr+ in case Map.lookup x m of+ Nothing -> tr+ Just tr' -> let tr'' = deleteSuffixes xs tr'+ in if null tr''+ then mkTrie v (Map.delete x m)+ else mkTrie v (Map.insert x tr'' m)+ -- O(m)-splitPrefix :: (Alt st a, Trie trie st map k)+splitPrefix :: forall trie map st k a .+ (Alt st a, Trie trie st map k) => trie map k a -> ([k], st a, trie map k a) splitPrefix = go DL.empty where+ go :: (Alt st a, Trie trie st map k)+ => DL.DList k -> trie map k a -> ([k], st a, trie map k a) go xs tr = case Map.singletonView (tMap tr) of Just (x,tr') -> go (xs `DL.snoc` x) tr'@@ -862,4 +893,4 @@ . showString "-> " . sk . showChar ' ' . go (i + lk + 4) f t)- (Map.toList m))+ (Map.toListKV m))
Data/ListTrie/Base/Classes.hs view
@@ -9,7 +9,6 @@ module Data.ListTrie.Base.Classes where import qualified Control.Applicative as A-import Control.Applicative (Applicative(..)) import Control.Monad (liftM2) import Data.Maybe (fromJust, isJust)
Data/ListTrie/Base/Map.hs view
@@ -1,29 +1,26 @@ -- File created: 2008-11-07 17:30:16 -{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}+{-# LANGUAGE CPP, MultiParamTypeClasses, FlexibleInstances #-} module Data.ListTrie.Base.Map ( Map(..), OrdMap(..) , AList, WrappedIntMap ) where -import Control.Applicative (pure, (<*>)) import Control.Arrow ((***), first, second) import Control.Monad (liftM, liftM2) import Data.Foldable (Foldable(..)) import Data.Function (on)-import Data.List ( foldl1'- , mapAccumL, nubBy, partition- , sort, sortBy- )+import Data.List (foldl1', mapAccumL, nubBy, partition, sort, sortBy) import Data.Ord (comparing) import Data.Traversable (Traversable(..), mapAccumR)-import qualified Data.IntMap as IM-import qualified Data.Map as M--import Prelude hiding ( foldl,foldl1,foldr,foldr1- , mapM,sequence- , null,lookup,filter -- for Haddock+import qualified Data.IntMap as IM+import qualified Data.Map as M+#if MIN_VERSION_containers(0,5,0)+import qualified Data.Map.Strict as M.Strict+#endif+import Prelude hiding ( filter, foldl, foldl1, foldr, foldr1, lookup, null+ , mapM, sequence ) import qualified Prelude @@ -41,7 +38,7 @@ -- -- * 'unionWithKey', 'differenceWithKey', 'intersectionWithKey' ----- * 'toList'+-- * 'toListKV' -- -- * 'empty' or 'fromList' or 'fromListWith' --@@ -87,9 +84,9 @@ filter :: (a -> Bool) -> m k a -> m k a - toList :: m k a -> [(k,a)]- fromList :: [(k,a)] -> m k a- fromListWith :: (a -> a -> a) -> [(k,a)] -> m k a+ toListKV :: m k a -> [(k,a)]+ fromListKV :: [(k,a)] -> m k a+ fromListKVWith :: (a -> a -> a) -> [(k,a)] -> m k a serializeToList :: m k a -> [(k,a)] deserializeFromList :: [(k,a)] -> m k a@@ -98,7 +95,7 @@ singletonView :: m k a -> Maybe (k,a) - empty = fromList []+ empty = fromListKV [] singleton k v = insert k v empty doubleton k v = insert k v .: singleton @@ -120,21 +117,21 @@ mapWithKey f = snd . mapAccumWithKey (\_ k v -> ((), f k v)) () mapAccum f = mapAccumWithKey (const . f) mapAccumWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z .- toList+ toListKV - filter p = fromList . Prelude.filter (p . snd) . toList+ filter p = fromListKV . Prelude.filter (p . snd) . toListKV -- | Should be strict in the keys- fromList = fromListWith const- fromListWith f = foldr (uncurry $ insertWith f) empty+ fromListKV = fromListKVWith const+ fromListKVWith f = foldr (uncurry $ insertWith f) empty - serializeToList = toList- deserializeFromList = fromList+ serializeToList = toListKV+ deserializeFromList = fromListKV singletonView m =- case toList m of+ case toListKV m of [x] -> Just x _ -> Nothing @@ -182,12 +179,12 @@ minViewWithKey m = case toAscList m of [] -> (Nothing, m)- (x:xs) -> (Just x, fromList xs)+ (x:xs) -> (Just x, fromListKV xs) maxViewWithKey m = case toDescList m of [] -> (Nothing, m)- (x:xs) -> (Just x, fromList xs)+ (x:xs) -> (Just x, fromListKV xs) findPredecessor m = fst . maxViewWithKey . fst . split m findSuccessor m = fst . minViewWithKey . snd . split m@@ -195,11 +192,11 @@ mapAccumAsc f = mapAccumAscWithKey (const . f) mapAccumDesc f = mapAccumDescWithKey (const . f) mapAccumAscWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z . toAscList mapAccumDescWithKey f z =- second fromList .+ second fromListKV . mapAccumL (\a (k,v) -> fmap ((,) k) (f a k v)) z . toDescList @@ -276,9 +273,9 @@ in (a', (k, v'))) z xs - toList (AL xs) = xs- fromList = AL . nubBy ((==) `on` fst)- fromListWith = AL .: go+ toListKV (AL xs) = xs+ fromListKV = AL . nubBy ((==) `on` fst)+ fromListKVWith = AL .: go where go _ [] = [] go f (x:xs) =@@ -301,8 +298,8 @@ instance Ord k => OrdMap AList k where ordCmp = const compare - toAscList = sortBy ( comparing fst) . toList- toDescList = sortBy (flip $ comparing fst) . toList+ toAscList = sortBy ( comparing fst) . toListKV+ toDescList = sortBy (flip $ comparing fst) . toListKV splitLookup k (AL xs) = let (ls,gs) = partition ((< k).fst) xs@@ -347,7 +344,11 @@ null = M.null lookup = M.lookup +#if MIN_VERSION_containers(0,5,0)+ insertWith = M.Strict.insertWith+#else insertWith = M.insertWith'+#endif update = M.update adjust = M.adjust@@ -369,9 +370,9 @@ filter = M.filter - toList = M.toList- fromList = M.fromList- fromListWith = M.fromListWith+ toListKV = M.toList+ fromListKV = M.fromList+ fromListKVWith = M.fromListWith serializeToList = M.toAscList deserializeFromList = M.fromDistinctAscList@@ -452,9 +453,9 @@ filter p (IMap x) = IMap $ IM.filter p x - toList (IMap m) = Prelude.map (first toEnum) . IM.toList $ m- fromList = IMap . IM.fromList . Prelude.map (first fromEnum)- fromListWith f = IMap . IM.fromListWith f . Prelude.map (first fromEnum)+ toListKV (IMap m) = Prelude.map (first toEnum) . IM.toList $ m+ fromListKV = IMap . IM.fromList . Prelude.map (first fromEnum)+ fromListKVWith f = IMap . IM.fromListWith f . Prelude.map (first fromEnum) serializeToList (IMap x) = Prelude.map (first toEnum) . IM.toAscList $ x deserializeFromList =
Data/ListTrie/Map.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a trie representing a map with list keys, -- generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the map and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the map and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the map. -- -- In addition, the trie's branching factor plays a part in almost every@@ -36,7 +36,6 @@ -- key: don't use the latter form of the function unless you need it. module Data.ListTrie.Map (MAP_EXPORTS) where -import Control.Applicative ((<*>),(<$>)) import Control.Arrow ((***), second) import Control.Monad (liftM2) import Data.Binary (Binary,get,put)@@ -44,10 +43,10 @@ import Data.Either (partitionEithers) import Data.Function (on) import qualified Data.Foldable as F+import qualified Data.List.NonEmpty as NE import qualified Data.Maybe as Maybe-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable(traverse))-import Prelude hiding (filter, foldl, foldr, lookup, map, null)+import Data.Semigroup (Semigroup(..), stimesIdempotent)+import Prelude hiding (filter, foldl, foldl', foldr, lookup, map, null) import qualified Prelude #if __GLASGOW_HASKELL__@@ -96,9 +95,14 @@ where compare = compare `on` toAscList +instance Map map k => Semigroup (TrieMap map k a) where+ (<>) = union+ sconcat = unions . NE.toList+ stimes = stimesIdempotent+ instance Map map k => Monoid (TrieMap map k a) where mempty = empty- mappend = union+ mappend = (<>) mconcat = unions instance Map map k => Functor (TrieMap map k) where@@ -978,6 +982,14 @@ -- * Trie-only operations +-- | @O(s)@. The map which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])+-- > == fromList [("ab",2),("abc",4)]+lookupPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+lookupPrefix = Base.lookupPrefix+ -- | @O(s)@. Prepends the given key to all the keys of the map. For example: -- -- > addPrefix "xa" (fromList [("a",1),("b",2)])@@ -985,7 +997,7 @@ addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a addPrefix = Base.addPrefix --- | @O(m)@. The map which contains all keys of which the given key is a+-- | @O(s)@. The map which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the map, an empty map is returned. For example: --@@ -1001,6 +1013,13 @@ deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a deletePrefix = Base.deletePrefix +-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- > == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+deleteSuffixes = Base.deleteSuffixes+ -- | @O(m)@. A triple containing the longest common prefix of all keys in the -- map, the value associated with that prefix, if any, and the map with that -- prefix removed from all the keys as well as the map itself. Examples:@@ -1028,8 +1047,7 @@ -- contains less than two keys, this function will return an empty map. -- -- If the longest common prefix of all keys in the trie is the empty list, this--- function is equivalent to 'children'. Otherwise, the result will always be a--- single-element map.+-- function is equivalent to 'children'. -- -- Examples: --
Data/ListTrie/Patricia/Base.hs view
@@ -1,8 +1,7 @@ -- File created: 2008-12-28 17:20:14 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies- , FlexibleContexts, ScopedTypeVariables, Rank2Types- , NoMonomorphismRestriction #-}+ , FlexibleContexts, ScopedTypeVariables, Rank2Types #-} module Data.ListTrie.Patricia.Base ( Trie(..)@@ -26,12 +25,12 @@ , fromList, fromListWith, fromListWith', fromListWithKey, fromListWithKey' , findMin, findMax, deleteMin, deleteMax, minView, maxView , findPredecessor, findSuccessor- , addPrefix, splitPrefix, deletePrefix, children, children1+ , lookupPrefix, addPrefix, deletePrefix, deleteSuffixes+ , splitPrefix, children, children1 , showTrieWith , eqComparePrefixes, ordComparePrefixes ) where -import Control.Applicative (Applicative(..), (<$>)) import Control.Arrow ((***), first) import Control.Exception (assert) import qualified Data.DList as DL@@ -564,7 +563,7 @@ PostFix (Right xs) -> goLeft tr1 tr2 xs dw a b =- let c = differenceWith j a b+ let c = go a b in if null c then Nothing else Just c mk v v' p m m' =@@ -974,7 +973,7 @@ p' = map f p in listSeq p' `seeq` (mkTrie v p' $- Map.fromListWith (unionW j) . map (f *** go) . Map.toList $ m)+ Map.fromListKVWith (unionW j) . map (f *** go) . Map.toListKV $ m) -- * Folding @@ -1027,7 +1026,7 @@ -- O(n m) toList :: (Boolable (st a), Trie trie st map k) => trie map k a -> [([k],a)]-toList = genericToList Map.toList DL.cons+toList = genericToList Map.toListKV DL.cons -- O(n m) toAscList :: (Boolable (st a), Trie trie st map k, OrdMap map k)@@ -1226,11 +1225,14 @@ error "Data.ListTrie.Patricia.Base.findPredecessor :: internal error" -- O(m)-findSuccessor :: (Boolable (st a), Trie trie st map k, OrdMap map k)+findSuccessor :: forall trie map st k a .+ (Boolable (st a), Trie trie st map k, OrdMap map k) => [k] -> trie map k a -> Maybe ([k], a) findSuccessor _ tr | null tr = Nothing findSuccessor xs_ tr_ = go xs_ tr_ where+ go :: (Boolable (st a), Trie trie st map k, OrdMap map k)+ => [k] -> trie map k a -> Maybe ([k], a) go xs tr = let (_,pre,m) = tParts tr in case comparePrefixes (Map.eqCmp m) pre xs of@@ -1259,13 +1261,34 @@ -- * Trie-only operations -- O(s)+lookupPrefix :: (Alt st a, Boolable (st a), Trie trie st map k)+ => [k] -> trie map k a -> trie map k a+lookupPrefix xs tr =+ let (_,pre,m) = tParts tr+ in case comparePrefixes (Map.eqCmp m) pre xs of+ DifferedAt _ _ _ -> empty+ Same -> tr+ PostFix (Left _) -> tr+ PostFix (Right (y:ys)) ->+ case Map.lookup y m of+ Nothing -> empty+ Just tr' -> let tr'' = lookupPrefix ys tr'+ (v',pre',m') = tParts tr''+ in if null tr''+ then tr''+ else mkTrie v' (pre ++ y : pre') m'+ _ ->+ error+ "Data.ListTrie.Patricia.Base.lookupPrefix :: internal error"++-- O(s) addPrefix :: (Alt st a, Trie trie st map k) => [k] -> trie map k a -> trie map k a addPrefix xs tr = let (v,pre,m) = tParts tr in mkTrie v (xs ++ pre) m --- O(m)+-- O(s) deletePrefix :: (Alt st a, Boolable (st a), Trie trie st map k) => [k] -> trie map k a -> trie map k a deletePrefix xs tr =@@ -1283,6 +1306,28 @@ error "Data.ListTrie.Patricia.Base.deletePrefix :: internal error" +-- O(s)+deleteSuffixes :: (Alt st a, Boolable (st a), Trie trie st map k)+ => [k] -> trie map k a -> trie map k a+deleteSuffixes xs tr =+ let (v,pre,m) = tParts tr+ in case comparePrefixes (Map.eqCmp m) pre xs of+ DifferedAt _ _ _ -> tr+ Same -> empty+ PostFix (Left _) -> empty+ PostFix (Right (y:ys)) ->+ case Map.lookup y m of+ Nothing -> tr+ Just tr' ->+ let tr'' = deleteSuffixes ys tr'+ in if null tr''+ then tryCompress$ mkTrie v pre (Map.delete y m)+ else mkTrie v pre (Map.insert y tr'' m)++ _ ->+ error+ "Data.ListTrie.Patricia.Base.deleteSuffixes :: internal error"+ -- O(1) splitPrefix :: (Alt st a, Boolable (st a), Trie trie st map k) => trie map k a -> ([k], st a, trie map k a)@@ -1328,7 +1373,7 @@ . showString "-> " . sk . showChar ' ' . go (i + lk + 4) f t)- (Map.toList m))+ (Map.toListKV m)) -- helpers
Data/ListTrie/Patricia/Map.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a Patricia trie representing a map with list -- keys, generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the map and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the map and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the map. -- -- In addition, the trie's branching factor plays a part in almost every@@ -36,7 +36,6 @@ -- key: don't use the latter form of the function unless you need it. module Data.ListTrie.Patricia.Map (MAP_EXPORTS) where -import Control.Applicative ((<*>),(<$>)) import Control.Arrow ((***), second) import Control.Monad (liftM3) import Data.Binary (Binary,get,put)@@ -44,10 +43,10 @@ import Data.Either (partitionEithers) import Data.Function (on) import qualified Data.Foldable as F+import qualified Data.List.NonEmpty as NE import qualified Data.Maybe as Maybe-import Data.Monoid (Monoid(..))-import Data.Traversable (Traversable(traverse))-import Prelude hiding (filter, foldl, foldr, lookup, map, null)+import Data.Semigroup (Semigroup(..), stimesIdempotent)+import Prelude hiding (filter, foldl, foldl', foldr, lookup, map, null) import qualified Prelude #if __GLASGOW_HASKELL__@@ -107,9 +106,14 @@ where compare = compare `on` toAscList +instance Map map k => Semigroup (TrieMap map k a) where+ (<>) = union+ sconcat = unions . NE.toList+ stimes = stimesIdempotent+ instance Map map k => Monoid (TrieMap map k a) where mempty = empty- mappend = union+ mappend = (<>) mconcat = unions instance Map map k => Functor (TrieMap map k) where@@ -996,6 +1000,14 @@ -- * Trie-only operations +-- | @O(s)@. The map which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])+-- > == fromList [("ab",2),("abc",4)]+lookupPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+lookupPrefix = Base.lookupPrefix+ -- | @O(s)@. Prepends the given key to all the keys of the map. For example: -- -- > addPrefix "xa" (fromList [("a",1),("b",2)])@@ -1003,7 +1015,7 @@ addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a addPrefix = Base.addPrefix --- | @O(m)@. The map which contains all keys of which the given key is a+-- | @O(s)@. The map which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the map, an empty map is returned. For example: --@@ -1019,6 +1031,13 @@ deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a deletePrefix = Base.deletePrefix +-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- > == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a+deleteSuffixes = Base.deleteSuffixes+ -- | @O(1)@. A triple containing the longest common prefix of all keys in the -- map, the value associated with that prefix, if any, and the map with that -- prefix removed from all the keys as well as the map itself. Examples:@@ -1046,8 +1065,7 @@ -- contains less than two keys, this function will return an empty map. -- -- If the longest common prefix of all keys in the trie is the empty list, this--- function is equivalent to 'children'. Otherwise, the result will always be a--- single-element map.+-- function is equivalent to 'children'. -- -- Examples: --
Data/ListTrie/Patricia/Set.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a Patricia trie representing a set of lists, -- generalized over any type of map from element values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the set and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the set and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the set. -- -- In addition, the trie's branching factor plays a part in almost every@@ -27,8 +27,9 @@ import Control.Monad (liftM3) import Data.Binary (Binary,get,put) import Data.Function (on)-import Data.Monoid (Monoid(..))-import Prelude hiding (filter, foldl, foldr, map, null)+import qualified Data.List.NonEmpty as NE+import Data.Semigroup (Semigroup(..), stimesIdempotent)+import Prelude hiding (filter, foldl, foldl', foldr, map, null) import qualified Prelude #if __GLASGOW_HASKELL__@@ -101,9 +102,14 @@ where compare = compare `on` unTS +instance Map map a => Semigroup (TrieSet map a) where+ (<>) = union+ sconcat = unions . NE.toList+ stimes = stimesIdempotent+ instance Map map a => Monoid (TrieSet map a) where mempty = empty- mappend = union+ mappend = (<>) mconcat = unions instance (Map map a, Show a) => Show (TrieSet map a) where@@ -367,13 +373,21 @@ -- * Trie-only operations +-- | @O(s)@. The set which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList ["a","ab","ac","abc"])+-- > == fromList ["ab","abc"]+lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a+lookupPrefix = TS .: Base.lookupPrefix .:. unTS+ -- | @O(s)@. Prepends the given key to all the keys of the set. For example: -- -- > addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"] addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a addPrefix = TS .: Base.addPrefix .:. unTS --- | @O(m)@. The set which contains all keys of which the given key is a+-- | @O(s)@. The set which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the set, an empty set is returned. For example: --@@ -388,6 +402,13 @@ deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a deletePrefix = TS .: Base.deletePrefix .:. unTS +-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- > == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a+deleteSuffixes = TS .: Base.deleteSuffixes .:. unTS+ -- | @O(1)@. A triple containing the longest common prefix of all keys in the -- set, whether that prefix was a member of the set, and the set with that -- prefix removed from all the keys as well as the set itself. Examples:@@ -413,8 +434,7 @@ -- contains less than two keys, this function will return an empty map. -- -- If the longest common prefix of all keys in the trie is the empty list, this--- function is equivalent to 'children'. Otherwise, the result will always be a--- single-element map.+-- function is equivalent to 'children'. -- -- Examples: --
Data/ListTrie/Set.hs view
@@ -8,8 +8,8 @@ -- | The base implementation of a trie representing a set of lists, generalized -- over any type of map from key values to tries. ----- Worst-case complexities are given in terms of @n@, @m@, and @k@. @n@ refers--- to the number of keys in the set and @m@ to their maximum length. @k@ refers+-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers+-- to the number of keys in the set and @m@ to their maximum length. @s@ refers -- to the length of a key given to the function, not any property of the set. -- -- In addition, the trie's branching factor plays a part in almost every@@ -27,8 +27,9 @@ import Control.Monad (liftM2) import Data.Binary (Binary,get,put) import Data.Function (on)-import Data.Monoid (Monoid(..))-import Prelude hiding (filter, foldl, foldr, map, null)+import qualified Data.List.NonEmpty as NE+import Data.Semigroup (Semigroup(..), stimesIdempotent)+import Prelude hiding (filter, foldl, foldl', foldr, map, null) import qualified Prelude #if __GLASGOW_HASKELL__@@ -96,9 +97,14 @@ where compare = compare `on` unTS +instance Map map a => Semigroup (TrieSet map a) where+ (<>) = union+ sconcat = unions . NE.toList+ stimes = stimesIdempotent+ instance Map map a => Monoid (TrieSet map a) where mempty = empty- mappend = union+ mappend = (<>) mconcat = unions instance (Map map a, Show a) => Show (TrieSet map a) where@@ -362,13 +368,21 @@ -- * Trie-only operations +-- | @O(s)@. The set which contains all keys of which the given key is a+-- prefix. For example:+--+-- > lookupPrefix "ab" (fromList ["a","ab","ac","abc"])+-- > == fromList ["ab","abc"]+lookupPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a+lookupPrefix = TS .: Base.lookupPrefix .:. unTS+ -- | @O(s)@. Prepends the given key to all the keys of the set. For example: -- -- > addPrefix "pre" (fromList ["a","b"]) == fromList ["prea","preb"] addPrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a addPrefix = TS .: Base.addPrefix .:. unTS --- | @O(m)@. The set which contains all keys of which the given key is a+-- | @O(s)@. The set which contains all keys of which the given key is a -- prefix, with the prefix removed from each key. If the given key is not a -- prefix of any key in the set, an empty set is returned. For example: --@@ -383,6 +397,13 @@ deletePrefix :: Map map a => [a] -> TrieSet map a -> TrieSet map a deletePrefix = TS .: Base.deletePrefix .:. unTS +-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:+--+-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])+-- > == fromList [("a",1),("ac",3),("b",4)]+deleteSuffixes :: Map map a => [a] -> TrieSet map a -> TrieSet map a+deleteSuffixes = TS .: Base.deleteSuffixes .:. unTS+ -- | @O(m)@. A triple containing the longest common prefix of all keys in the -- set, whether that prefix was a member of the set, and the set with that -- prefix removed from all the keys as well as the set itself. Examples:@@ -408,8 +429,7 @@ -- contains less than two keys, this function will return an empty map. -- -- If the longest common prefix of all keys in the trie is the empty list, this--- function is equivalent to 'children'. Otherwise, the result will always be a--- single-element map.+-- function is equivalent to 'children'. -- -- Examples: --
LICENSE.txt view
@@ -2,7 +2,7 @@ are held by whoever wrote the code in question: see CREDITS.txt for a list of authors. -Copyright (c) 2008-2010 <authors>+Copyright (c) 2008-2018 <authors> All rights reserved. Redistribution and use in source and binary forms, with or without
+ README.md view
@@ -0,0 +1,9 @@+# list-tries++[](https://github.com/arybczak/list-tries/actions?query=branch%3Amaster)+[](https://hackage.haskell.org/package/list-tries)+[](https://packdeps.haskellers.com/feed?needle=andrzej@rybczak.net)+[](https://www.stackage.org/lts/package/list-tries)+[](https://www.stackage.org/nightly/package/list-tries)++Tries and Patricia tries: finite sets and maps for list keys.
− Setup.hs
@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain
headers/exports.h view
@@ -1,134 +1,136 @@ -- File created: 2008-12-30 18:33:18 #define SET_EXPORTS \- {- * Set type -} \- TrieSet, \- {- * Construction -} \- empty, singleton, \- \- {- * Modification -} \- insert, delete, \- \- {- * Querying -} \- null, size, size', member, notMember, \- \- {- ** Subsets -} \- isSubsetOf, isProperSubsetOf, \- \- {- * Combination -} \- union, unions, difference, intersection, \- \- {- * Filtering -} \- filter, partition, \- \- {- * Mapping -} \- map, mapIn, \- \- {- * Folding -} \- foldr, foldrAsc, foldrDesc, \- foldl, foldlAsc, foldlDesc, \- foldl', foldlAsc', foldlDesc', \- \- {- * Conversion to and from lists -} \- toList, toAscList, toDescList, fromList, \- \- {- * Ordering-sensitive operations -} \- {- ** Minimum and maximum -} \- minView, maxView, findMin, findMax, deleteMin, deleteMax, \- \- {- ** Predecessor and successor -} \- split, splitMember, \- findPredecessor, findSuccessor, \- \- {- * Trie-specific operations -} \- {- $trie-only-ops -} \- addPrefix, deletePrefix, splitPrefix, children, children1, \- \- {- * Visualization -} \- showTrie+ {- * Set type -} \+ TrieSet, \+ {- * Construction -} \+ empty, singleton, \+ \+ {- * Modification -} \+ insert, delete, \+ \+ {- * Querying -} \+ null, size, size', member, notMember, \+ \+ {- ** Subsets -} \+ isSubsetOf, isProperSubsetOf, \+ \+ {- * Combination -} \+ union, unions, difference, intersection, \+ \+ {- * Filtering -} \+ filter, partition, \+ \+ {- * Mapping -} \+ map, mapIn, \+ \+ {- * Folding -} \+ foldr, foldrAsc, foldrDesc, \+ foldl, foldlAsc, foldlDesc, \+ foldl', foldlAsc', foldlDesc', \+ \+ {- * Conversion to and from lists -} \+ toList, toAscList, toDescList, fromList, \+ \+ {- * Ordering-sensitive operations -} \+ {- ** Minimum and maximum -} \+ minView, maxView, findMin, findMax, deleteMin, deleteMax, \+ \+ {- ** Predecessor and successor -} \+ split, splitMember, \+ findPredecessor, findSuccessor, \+ \+ {- * Trie-specific operations -} \+ {- $trie-only-ops -} \+ lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \+ splitPrefix, children, children1, \+ \+ {- * Visualization -} \+ showTrie #define MAP_EXPORTS \- {- * Map type -} \- TrieMap, \- \- {- * Construction -} \- empty, singleton, \- \- {- * Modification -} \- insert, insert', insertWith, insertWith', \- delete, \- update, updateLookup, \- adjust, adjust', alter, alter', \- \- {- * Querying -} \- null, size, size', member, notMember, \- lookup, lookupWithDefault, \- \- {- ** Submaps -} \- isSubmapOf, isSubmapOfBy, \- isProperSubmapOf, isProperSubmapOfBy, \- \- {- * Combination -} \- {- ** Union -} \- union, union', unions, unions', \- unionWith, unionWithKey, unionsWith, unionsWithKey, \- unionWith', unionWithKey', unionsWith', unionsWithKey', \- \- {- ** Difference -} \- difference, differenceWith, differenceWithKey, \- \- {- ** Intersection -} \- intersection, intersection', \- intersectionWith, intersectionWithKey, \- intersectionWith', intersectionWithKey', \- \- {- * Filtering -} \- filter, filterWithKey, partition, partitionWithKey, \- mapMaybe, mapMaybeWithKey, mapEither, mapEitherWithKey, \- \- {- * Mapping -} \- {- ** Values -} \- map, map', mapWithKey, mapWithKey', \- \- {- ** Keys -} \- mapKeys, mapKeysWith, \- mapInKeys, mapInKeys', mapInKeysWith, mapInKeysWith', \- \- {- ** With accumulation -} \- mapAccum, mapAccumWithKey, \- mapAccum', mapAccumWithKey', \- mapAccumAsc, mapAccumAscWithKey, \- mapAccumAsc', mapAccumAscWithKey', \- mapAccumDesc, mapAccumDescWithKey, \- mapAccumDesc', mapAccumDescWithKey', \- \- {- * Folding -} \- foldr, foldrWithKey, \- foldrAsc, foldrAscWithKey, \- foldrDesc, foldrDescWithKey, \- foldl, foldlWithKey, \- foldlAsc, foldlAscWithKey, \- foldlDesc, foldlDescWithKey, \- foldl', foldlWithKey', \- foldlAsc', foldlAscWithKey', \- foldlDesc', foldlDescWithKey', \- \- {- * Conversion to and from lists -} \- toList, toAscList, toDescList, fromList, \- fromListWith, fromListWithKey, \- fromListWith', fromListWithKey', \- \- {- * Ordering-sensitive operations -} \- {- ** Minimum and maximum -} \- minView, maxView, findMin, findMax, deleteMin, deleteMax, \- \- {- ** Predecessor and successor -} \- split, splitLookup, \- findPredecessor, findSuccessor, \- \- {- * Trie-specific operations -} \- {- $trie-only-ops -} \- addPrefix, deletePrefix, splitPrefix, children, children1, \- \- {- * Visualization -} \- showTrie, showTrieWith+ {- * Map type -} \+ TrieMap, \+ \+ {- * Construction -} \+ empty, singleton, \+ \+ {- * Modification -} \+ insert, insert', insertWith, insertWith', \+ delete, \+ update, updateLookup, \+ adjust, adjust', alter, alter', \+ \+ {- * Querying -} \+ null, size, size', member, notMember, \+ lookup, lookupWithDefault, \+ \+ {- ** Submaps -} \+ isSubmapOf, isSubmapOfBy, \+ isProperSubmapOf, isProperSubmapOfBy, \+ \+ {- * Combination -} \+ {- ** Union -} \+ union, union', unions, unions', \+ unionWith, unionWithKey, unionsWith, unionsWithKey, \+ unionWith', unionWithKey', unionsWith', unionsWithKey', \+ \+ {- ** Difference -} \+ difference, differenceWith, differenceWithKey, \+ \+ {- ** Intersection -} \+ intersection, intersection', \+ intersectionWith, intersectionWithKey, \+ intersectionWith', intersectionWithKey', \+ \+ {- * Filtering -} \+ filter, filterWithKey, partition, partitionWithKey, \+ mapMaybe, mapMaybeWithKey, mapEither, mapEitherWithKey, \+ \+ {- * Mapping -} \+ {- ** Values -} \+ map, map', mapWithKey, mapWithKey', \+ \+ {- ** Keys -} \+ mapKeys, mapKeysWith, \+ mapInKeys, mapInKeys', mapInKeysWith, mapInKeysWith', \+ \+ {- ** With accumulation -} \+ mapAccum, mapAccumWithKey, \+ mapAccum', mapAccumWithKey', \+ mapAccumAsc, mapAccumAscWithKey, \+ mapAccumAsc', mapAccumAscWithKey', \+ mapAccumDesc, mapAccumDescWithKey, \+ mapAccumDesc', mapAccumDescWithKey', \+ \+ {- * Folding -} \+ foldr, foldrWithKey, \+ foldrAsc, foldrAscWithKey, \+ foldrDesc, foldrDescWithKey, \+ foldl, foldlWithKey, \+ foldlAsc, foldlAscWithKey, \+ foldlDesc, foldlDescWithKey, \+ foldl', foldlWithKey', \+ foldlAsc', foldlAscWithKey', \+ foldlDesc', foldlDescWithKey', \+ \+ {- * Conversion to and from lists -} \+ toList, toAscList, toDescList, fromList, \+ fromListWith, fromListWithKey, \+ fromListWith', fromListWithKey', \+ \+ {- * Ordering-sensitive operations -} \+ {- ** Minimum and maximum -} \+ minView, maxView, findMin, findMax, deleteMin, deleteMax, \+ \+ {- ** Predecessor and successor -} \+ split, splitLookup, \+ findPredecessor, findSuccessor, \+ \+ {- * Trie-specific operations -} \+ {- $trie-only-ops -} \+ lookupPrefix, addPrefix, deletePrefix, deleteSuffixes, \+ splitPrefix, children, children1, \+ \+ {- * Visualization -} \+ showTrie, showTrieWith
list-tries.cabal view
@@ -1,7 +1,6 @@-Cabal-Version: >= 1.6-+Cabal-Version: 3.0 Name: list-tries-Version: 0.4.3+Version: 0.6.7.1 Homepage: http://iki.fi/matti.niemenmaa/list-tries/ Synopsis: Tries and Patricia tries: finite sets and maps for list keys Category: Data, Data Structures@@ -23,30 +22,30 @@ Data.IntMap respectively. Author: Matti Niemenmaa-Maintainer: Matti Niemenmaa <matti.niemenmaa+list-tries@iki.fi>-License: BSD3+Maintainer: Andrzej Rybczak <andrzej@rybczak.net>+License: BSD-3-Clause License-File: LICENSE.txt--Build-Type: Simple+Tested-With: GHC == { 8.10.7, 9.0.2, 9.2.8, 9.4.8, 9.6.5, 9.8.2, 9.10.1 } -Extra-Source-Files: CHANGELOG.txt+Extra-Source-Files: README.md+ CHANGELOG.md CREDITS.txt headers/*.h tests/README.txt tests/*.hs tests/Tests/*.hs -flag testing- description: Enable building a test executable- default: False+source-repository head+ type: git+ location: https://github.com/arybczak/list-tries Library- Extensions: CPP+ Build-Depends: base >= 4.14 && < 5+ , binary >= 0.5 && < 0.11+ , containers >= 0.4 && < 0.8+ , dlist >= 0.4 && < 1.1 - Build-Depends: base >= 3 && < 4.7- , containers >= 0.3 && < 0.6- , dlist >= 0.4 && < 0.6- , binary >= 0.5 && < 0.7+ ghc-options: -Wall -Wextra -Wno-dodgy-imports Exposed-Modules: Data.ListTrie.Base.Map Data.ListTrie.Map@@ -73,54 +72,51 @@ Include-Dirs: headers -executable list-tries-tests- if !flag(testing)- buildable: False+ Default-language: Haskell2010 + Other-Extensions: CPP+ FlexibleContexts+ FlexibleInstances+ FunctionalDependencies+ MultiParamTypeClasses+ Rank2Types+ ScopedTypeVariables+ UndecidableInstances++Test-Suite list-tries-tests+ type: exitcode-stdio-1.0++ hs-source-dirs: tests main-is: Main.hs- hs-source-dirs: ., tests- Extensions: CPP - Build-Depends: base >= 3 && < 4.7- , containers >= 0.3 && < 0.6- , dlist >= 0.4 && < 0.6- , binary >= 0.5 && < 0.7+ if impl(ghc >= 9.8)+ ghc-options: -Wno-x-partial - if flag(testing)- Build-Depends: template-haskell >= 2.3 && < 2.9- , HUnit >= 1.2 && < 1.3- , QuickCheck >= 2.1 && < 2.6- , test-framework >= 0.2 && < 0.7- , test-framework-hunit >= 0.2 && < 0.3- , test-framework-quickcheck2 >= 0.2 && < 0.3- , ChasingBottoms >= 1.2 && < 1.4+ Build-Depends: list-tries+ , base < 5+ , binary+ , template-haskell >= 2.16 && < 2.23+ , HUnit+ , QuickCheck+ , test-framework+ , test-framework-hunit+ , test-framework-quickcheck2+ , ChasingBottoms - Other-Modules: Data.ListTrie.Base.Map- Data.ListTrie.Map- Data.ListTrie.Map.Eq- Data.ListTrie.Map.Ord- Data.ListTrie.Map.Enum- Data.ListTrie.Set- Data.ListTrie.Set.Eq- Data.ListTrie.Set.Ord- Data.ListTrie.Set.Enum- Data.ListTrie.Patricia.Map- Data.ListTrie.Patricia.Map.Eq- Data.ListTrie.Patricia.Map.Ord- Data.ListTrie.Patricia.Map.Enum- Data.ListTrie.Patricia.Set- Data.ListTrie.Patricia.Set.Eq- Data.ListTrie.Patricia.Set.Ord- Data.ListTrie.Patricia.Set.Enum- Data.ListTrie.Base- Data.ListTrie.Base.Classes- Data.ListTrie.Base.Map.Internal- Data.ListTrie.Patricia.Base- Data.ListTrie.Util- Tests.Base+ Other-Modules: Tests.Base Tests.Cases Tests.Properties Tests.Strictness Tests.TH - Include-Dirs: headers+ Default-language: Haskell2010++ Other-Extensions: CPP+ EmptyDataDecls+ FlexibleContexts+ FlexibleInstances+ FunctionalDependencies+ MultiParamTypeClasses+ NoMonomorphismRestriction+ PatternGuards+ TemplateHaskell
tests/Tests/Cases.hs view
@@ -23,8 +23,6 @@ import qualified Data.ListTrie.Patricia.Map.Ord import qualified Data.ListTrie.Patricia.Map.Enum -import Data.ListTrie.Util- import Tests.TH $(makeFunc allTries ["null","empty"] [d|@@ -143,7 +141,7 @@ b = fromList $ zip bl [length al..] in intersectionWithKey (\k vl vr -> length k - vl + vr) a b == fromList (zip ["cat","caterers"] $- zipWith3 (join (.:) (+) . negate)+ zipWith3 (\a b c -> b + c - a) [1..] [length al..] (map length al)) |]) $(makeFunc mapsOnly ["fromList","intersectionWithKey"] [d|
tests/Tests/Properties.hs view
@@ -415,7 +415,7 @@ let (k,b,_) = splitPrefix (t :: TrieType) in t == ((if b then insert k else id) . addPrefix k . unions $ map (uncurry $ addPrefix . return)- (Map.toList $ children t))+ (Map.toListKV $ children t)) |]) $(makeFunc mapsOnly ["addPrefix","splitPrefix","children","unions","insert"] [d|@@ -423,7 +423,7 @@ let (k,mv,_) = splitPrefix (t :: TrieType) in t == ((case mv of Just v -> insert k v; _ -> id) . addPrefix k . unions $ map (uncurry $ addPrefix . return)- (Map.toList $ children t))+ (Map.toListKV $ children t)) |]) -- Deleting an added prefix should change nothing@@ -433,7 +433,32 @@ in deletePrefix k (addPrefix k t) == (t :: TrieType) |]) +-- lookupPrefix k == addPrefix k . deletePrefix k if the result is nonempty+$(makeFunc allTries ["lookupPrefix","addPrefix","deletePrefix","null"] [d|+ prop_prefixOps6 lookupPrefix addPrefix deletePrefix null t k_ =+ let k = unArb k_+ t' = lookupPrefix k (t :: TrieType)+ in null t' || t' == addPrefix k (deletePrefix k t)+ |]) +-- The result of lookupPrefix should always be a subset of the original.+$(makeFunc setsOnly ["lookupPrefix","isSubsetOf"] [d|+ prop_prefixOps7_s lookupPrefix isSubsetOf t k =+ lookupPrefix (unArb k) (t :: TrieType) `isSubsetOf` t+ |])+$(makeFunc mapsOnly ["lookupPrefix","isSubmapOf"] [d|+ prop_prefixOps7_m lookupPrefix isSubmapOf t k =+ lookupPrefix (unArb k) (t :: TrieType) `isSubmapOf` t+ |])++-- deleteSuffixes k t == difference t (lookupPrefix k t)+$(makeFunc allTries ["deleteSuffixes","difference","lookupPrefix"] [d|+ prop_prefixOps8 deleteSuffixes lookupPrefix difference t k_ =+ let k = unArb k_+ in deleteSuffixes k (t :: TrieType) == difference t (lookupPrefix k t)+ |])++ -- The monoid laws: associativity, left identity, right identity $(makeFunc allTries [] [d| prop_monoidLaw1 x y z =@@ -540,6 +565,10 @@ , $(makeProps setsOnly "prop_prefixOps4_s") , $(makeProps mapsOnly "prop_prefixOps4_m") , $(makeProps allTries "prop_prefixOps5")+ , $(makeProps allTries "prop_prefixOps6")+ , $(makeProps setsOnly "prop_prefixOps7_s")+ , $(makeProps mapsOnly "prop_prefixOps7_m")+ , $(makeProps allTries "prop_prefixOps8") , $(makeProps allTries "prop_monoidLaw1") , $(makeProps allTries "prop_monoidLaw2") , $(makeProps allTries "prop_monoidLaw3")
tests/Tests/Strictness.hs view
@@ -9,20 +9,13 @@ import Test.Framework.Providers.HUnit (testCase) import Test.HUnit (assert) -import qualified Data.ListTrie.Set.Eq-import qualified Data.ListTrie.Set.Ord-import qualified Data.ListTrie.Set.Enum import qualified Data.ListTrie.Map.Eq import qualified Data.ListTrie.Map.Ord import qualified Data.ListTrie.Map.Enum-import qualified Data.ListTrie.Patricia.Set.Eq-import qualified Data.ListTrie.Patricia.Set.Ord-import qualified Data.ListTrie.Patricia.Set.Enum import qualified Data.ListTrie.Patricia.Map.Eq import qualified Data.ListTrie.Patricia.Map.Ord import qualified Data.ListTrie.Patricia.Map.Enum -import Tests.Base import Tests.TH -- size doesn't evaluate the values but it does traverse the whole trie
tests/Tests/TH.hs view
@@ -1,6 +1,6 @@ -- File created: 2009-01-09 13:57:13 -{-# LANGUAGE EmptyDataDecls, PatternGuards, TemplateHaskell #-}+{-# LANGUAGE CPP, EmptyDataDecls, PatternGuards, TemplateHaskell #-} module Tests.TH ( Module(..)@@ -115,14 +115,22 @@ (expandE m e) (fmap (expandE m) me2) expandE m (LamE pats e) = LamE pats (expandE m e)+#if MIN_VERSION_template_haskell(2,16,0)+ expandE m (TupE es) = TupE (map (fmap $ expandE m) es)+#else expandE m (TupE es) = TupE (map (expandE m) es)+#endif expandE m (CondE e1 e2 e3) = CondE (expandE m e1) (expandE m e2) (expandE m e3) expandE m (LetE decs e) = LetE (map (expandDec m) decs) (expandE m e) expandE m (CaseE e matches) = CaseE (expandE m e) (map (expandMatch m) matches)+#if MIN_VERSION_template_haskell(2,17,0)+ expandE m (DoE mmn stmts) = DoE mmn (map (expandStmt m) stmts)+#else expandE m (DoE stmts) = DoE (map (expandStmt m) stmts)+#endif expandE m (CompE stmts) = CompE (map (expandStmt m) stmts) expandE m (SigE e t) = SigE (expandE m e) (replaceTypes m t) expandE m (RecConE name fexps) = RecConE name (map (expandFieldExp m) fexps)