pred-trie 0.0.4 → 0.0.5

raw patch · 5 files changed

+73/−61 lines, 5 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• pred-trie.cabal +1/−1
• src/Data/Trie/Pred/Disjoint.hs +5/−5
• src/Data/Trie/Pred/Disjoint/Tail.hs +30/−24
• src/Data/Trie/Pred/Unified.hs +5/−5
• src/Data/Trie/Pred/Unified/Tail.hs +32/−26

@@ -1,5 +1,5 @@ Name:                   pred-trie-Version:                0.0.4+Version:                0.0.5 Author:                 Athan Clark <athan.clark@gmail.com> Maintainer:             Athan Clark <athan.clark@gmail.com> License:                BSD3

@@ -7,22 +7,22 @@   -- | A Rooted, predicate, disjointly indexed trie-data RPDTrie p t x = Rooted (Maybe x) [NDPTrie p t x]+data RDPTrie p t x = Rooted (Maybe x) [DPTrie p t x] -instance (Eq p, Eq t) => Monoid (RPDTrie p t x) where+instance (Eq p, Eq t) => Monoid (RDPTrie p t x) where   mempty = Rooted Nothing []   mappend = Data.Trie.Pred.Disjoint.merge -merge :: (Eq p, Eq t) => RPDTrie p t x -> RPDTrie p t x -> RPDTrie p t x+merge :: (Eq p, Eq t) => RDPTrie p t x -> RDPTrie p t x -> RDPTrie p t x merge (Rooted mx xs) (Rooted my ys) =   Rooted my $ foldr go [] $ xs ++ ys   where-    go :: (Eq p, Eq t) => NDPTrie p t x -> [NDPTrie p t x] -> [NDPTrie p t x]+    go :: (Eq p, Eq t) => DPTrie p t x -> [DPTrie p t x] -> [DPTrie p t x]     go a [] = [a]     go a (b:bs) | ND.areDisjoint a b =          a : b : bs                 | otherwise          = (ND.merge a b) : bs -lookup :: (Eq t) => [t] -> RPDTrie p t x -> Maybe x+lookup :: (Eq t) => [t] -> RDPTrie p t x -> Maybe x lookup [] (Rooted mx _) = mx lookup ts (Rooted _ xs) = getFirst $ map (ND.lookup $ NE.fromList ts) xs   where

@@ -3,7 +3,7 @@   #-}  module Data.Trie.Pred.Disjoint.Tail-  ( NDPTrie (..)+  ( DPTrie (..)   , lookup   , merge   , areDisjoint@@ -15,48 +15,48 @@   -data NDPTrie p t x where-  NDMore :: t-         -> Maybe x-         -> [NDPTrie p t x]-         -> NDPTrie p t x-  NDPred :: p-         -> (t -> Maybe r)-         -> Maybe (r -> x)-         -> [NDPTrie p t (r -> x)]-         -> NDPTrie p t x+data DPTrie p t x where+  DMore :: t+        -> Maybe x+        -> [DPTrie p t x]+        -> DPTrie p t x+  DPred :: p+        -> (t -> Maybe r)+        -> Maybe (r -> x)+        -> [DPTrie p t (r -> x)]+        -> DPTrie p t x   -- | Overwrites when similar, leaves untouched when not-merge :: (Eq p, Eq t) => NDPTrie p t x -> NDPTrie p t x -> NDPTrie p t x-merge xx@(NDMore t mx xs) yy@(NDMore p my ys)-  | t == p = NDMore p my $ foldr go [] $ xs ++ ys+merge :: (Eq p, Eq t) => DPTrie p t x -> DPTrie p t x -> DPTrie p t x+merge xx@(DMore t mx xs) yy@(DMore p my ys)+  | t == p = DMore p my $ foldr go [] $ xs ++ ys   | otherwise = xx   where-    go :: (Eq p, Eq t) => NDPTrie p t x -> [NDPTrie p t x] -> [NDPTrie p t x]+    go :: (Eq p, Eq t) => DPTrie p t x -> [DPTrie p t x] -> [DPTrie p t x]     go a [] = [a]     go a (b:bs) | areDisjoint a b =       a : b : bs                 | otherwise       = (merge a b) : bs-merge xx@(NDPred t q mrx xrs) yy@(NDPred p w mry yrs)+merge xx@(DPred t q mrx xrs) yy@(DPred p w mry yrs)   | t == p = yy   | otherwise = xx-merge xx@(NDMore t mx xs) yy@(NDPred p w mrx xrs) = yy-merge xx@(NDPred t q mrx xrs) yy@(NDMore p my ys) = yy+merge xx@(DMore t mx xs) yy@(DPred p w mrx xrs) = yy+merge xx@(DPred t q mrx xrs) yy@(DMore p my ys) = yy  -areDisjoint :: (Eq p, Eq t) => NDPTrie p t x -> NDPTrie p t x -> Bool-areDisjoint (NDMore t _ _)    (NDMore p _ _)    = t == p-areDisjoint (NDPred t _ _ _)  (NDPred p _ _ _)  = t == p+areDisjoint :: (Eq p, Eq t) => DPTrie p t x -> DPTrie p t x -> Bool+areDisjoint (DMore t _ _)    (DMore p _ _)    = t == p+areDisjoint (DPred t _ _ _)  (DPred p _ _ _)  = t == p areDisjoint _ _ = True  -lookup :: Eq t => NonEmpty t -> NDPTrie p t x -> Maybe x-lookup (t:|ts) (NDMore t' mx xs)+lookup :: Eq t => NonEmpty t -> DPTrie p t x -> Maybe x+lookup (t:|ts) (DMore t' mx xs)   | t == t' = case ts of     [] -> mx     _  -> getFirst $ map (lookup $ NE.fromList ts) xs   | otherwise = Nothing-lookup (t:|ts) (NDPred _ p mrx xrs) =+lookup (t:|ts) (DPred _ p mrx xrs) =   p t >>=     \r -> case ts of       [] -> ($ r) <$> mrx@@ -67,3 +67,9 @@ getFirst [] = Nothing getFirst (Nothing:xs) = getFirst xs getFirst (Just x :xs) = Just x+++buildLitSingletonTail :: NonEmpty t -> x -> DPTrie p t x+buildLitSingletonTail (t:|[]) x = DMore t (Just x) []+buildLitSingletonTail (t:|ts) x = DMore t Nothing  [buildLitSingletonTail (NE.fromList ts) x]+

@@ -6,22 +6,22 @@ import qualified Data.List.NonEmpty as NE  -data RPUTrie t x = Rooted (Maybe x) [NUPTrie t x]+data RUPTrie t x = Rooted (Maybe x) [UPTrie t x] -instance (Eq t) => Monoid (RPUTrie t x) where+instance (Eq t) => Monoid (RUPTrie t x) where   mempty = Rooted Nothing []   mappend = Data.Trie.Pred.Unified.merge -merge :: (Eq t) => RPUTrie t x -> RPUTrie t x -> RPUTrie t x+merge :: (Eq t) => RUPTrie t x -> RUPTrie t x -> RUPTrie t x merge (Rooted mx xs) (Rooted my ys) =   Rooted my $ foldr go [] $ xs ++ ys   where-    go :: (Eq t) => NUPTrie t x -> [NUPTrie t x] -> [NUPTrie t x]+    go :: (Eq t) => UPTrie t x -> [UPTrie t x] -> [UPTrie t x]     go a [] = [a]     go a (b:bs) | NU.areDisjoint a b =          a : b : bs                 | otherwise          = (NU.merge a b) : bs -lookup :: (Eq t) => [t] -> RPUTrie t x -> Maybe x+lookup :: (Eq t) => [t] -> RUPTrie t x -> Maybe x lookup [] (Rooted mx _) = mx lookup ts (Rooted _ xs) = getFirst $ map (NU.lookup $ NE.fromList ts) xs   where

@@ -3,7 +3,7 @@   #-}  module Data.Trie.Pred.Unified.Tail-  ( NUPTrie (..)+  ( UPTrie (..)   , lookup   , merge   , areDisjoint@@ -15,53 +15,53 @@   -data NUPTrie t x where-  NUMore :: t-         -> Maybe x-         -> [NUPTrie t x]-         -> NUPTrie t x-  NUPred :: t-         -> (t -> Maybe r)-         -> Maybe (r -> x)-         -> [NUPTrie t (r -> x)]-         -> NUPTrie t x+data UPTrie t x where+  UMore :: t+        -> Maybe x+        -> [UPTrie t x]+        -> UPTrie t x+  UPred :: t+        -> (t -> Maybe r)+        -> Maybe (r -> x)+        -> [UPTrie t (r -> x)]+        -> UPTrie t x   -- | Overwrites when similar, leaves untouched when not-merge :: (Eq t) => NUPTrie t x -> NUPTrie t x -> NUPTrie t x-merge xx@(NUMore t mx xs) yy@(NUMore p my ys)-  | t == p = NUMore p my $ foldr go [] $ xs ++ ys+merge :: (Eq t) => UPTrie t x -> UPTrie t x -> UPTrie t x+merge xx@(UMore t mx xs) yy@(UMore p my ys)+  | t == p = UMore p my $ foldr go [] $ xs ++ ys   | otherwise = xx   where-    go :: (Eq t) => NUPTrie t x -> [NUPTrie t x] -> [NUPTrie t x]+    go :: (Eq t) => UPTrie t x -> [UPTrie t x] -> [UPTrie t x]     go a [] = [a]     go a (b:bs) | areDisjoint a b =       a : b : bs                 | otherwise       = (merge a b) : bs-merge xx@(NUPred t q mrx xrs) yy@(NUPred p w mry yrs)+merge xx@(UPred t q mrx xrs) yy@(UPred p w mry yrs)   | t == p = yy   | otherwise = xx-merge xx@(NUMore t mx xs) yy@(NUPred p w mrx xrs)+merge xx@(UMore t mx xs) yy@(UPred p w mrx xrs)   | t == p = yy -- predicate children are incompatible   | otherwise = xx-merge xx@(NUPred t q mrx xrs) yy@(NUMore p my ys)+merge xx@(UPred t q mrx xrs) yy@(UMore p my ys)   | t == p = yy   | otherwise = xx  -areDisjoint :: (Eq t) => NUPTrie t x -> NUPTrie t x -> Bool-areDisjoint (NUMore t _ _)    (NUMore p _ _)    = t == p-areDisjoint (NUPred t _ _ _)  (NUPred p _ _ _)  = t == p-areDisjoint (NUPred t _ _ _)  (NUMore p _ _)    = t == p-areDisjoint (NUMore t _ _)    (NUPred p _ _ _)  = t == p+areDisjoint :: (Eq t) => UPTrie t x -> UPTrie t x -> Bool+areDisjoint (UMore t _ _)    (UMore p _ _)    = t == p+areDisjoint (UPred t _ _ _)  (UPred p _ _ _)  = t == p+areDisjoint (UPred t _ _ _)  (UMore p _ _)    = t == p+areDisjoint (UMore t _ _)    (UPred p _ _ _)  = t == p  -lookup :: Eq t => NonEmpty t -> NUPTrie t x -> Maybe x-lookup (t:|ts) (NUMore t' mx xs)+lookup :: Eq t => NonEmpty t -> UPTrie t x -> Maybe x+lookup (t:|ts) (UMore t' mx xs)   | t == t' = case ts of     [] -> mx     _  -> getFirst $ map (lookup $ NE.fromList ts) xs   | otherwise = Nothing-lookup (t:|ts) (NUPred _ p mrx xrs) =+lookup (t:|ts) (UPred _ p mrx xrs) =   p t >>=     \r -> case ts of       [] -> ($ r) <$> mrx@@ -72,3 +72,9 @@ getFirst [] = Nothing getFirst (Nothing:xs) = getFirst xs getFirst (Just x :xs) = Just x+++buildLitSingletonTail :: NonEmpty t -> x -> UPTrie t x+buildLitSingletonTail (t:|[]) x = UMore t (Just x) []+buildLitSingletonTail (t:|ts) x = UMore t Nothing  [buildLitSingletonTail (NE.fromList ts) x]+