mmsyn2 0.1.5.0 → 0.1.6.0

raw patch · 3 files changed

+30/−15 lines, 3 filesdep ~basedep ~vectorPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base, vector

API changes (from Hackage documentation)

Files

• CaseBi.hs +23/−13
• ChangeLog.md +5/−0
• mmsyn2.cabal +2/−2

@@ -19,7 +19,7 @@   filterP ) where -import qualified Data.Vector as V (Vector,unsafeHead,unsafeLast,unsafeSlice,length,(!),fromList,map)+import qualified Data.Vector as V (Vector,unsafeIndex,unsafeSlice,length,fromList,map) import qualified Data.List as L (groupBy,nubBy) --import Prelude -- (Bool,Eq,Ord,map,(>=),(<=),(>),(<),(==),(&&),(.),(++),(-),($),filter,otherwise,fst,snd,quot,not,null,dropWhile,concatMap,take,seq,undefined)@@ -35,7 +35,7 @@ -- >   _  -> defaultValue --  -- If we follow a lot of teaching materials that explain the workflow of the construction we think that the complexity of it is about /O(n)/ for the transformation of @a@ to @b@ here. --- David Feuer (david.feuer@gmail.com) said that 'case ... of' is already optimized in GHC. Some benchmarks show that its behaviour  tends to be about of /O(log n)/ complexity, the same as+-- David Feuer (david.feuer (at) gmail.com) said that 'case ... of' is already optimized in GHC. Some benchmarks show that its behaviour  tends to be about of /O(log n)/ complexity, the same as -- the proposed function getBFst'. Nevertheless, the last one shows better performance in some situations, is rather general and can be used for another data representation. -- Therefore, it can be preferred in some situations. getBFst' uses binary search algorithm and a Vector (a, b) as somewhat like a complicated filter or like a special sieve. -- The @Vector (a, b)@ must be sorted in ascending order here for the algorithm to be used correctly. For this you can use @@ -51,16 +51,18 @@ -- >  ... -- >  an -> bn -- -getBFst' :: (Ord a) => (b, V.Vector (a, b)) -- ^ a default value that can be substituted if there is no correspendence in the set of @(a, b)@ tuples (the 'otherwise' or irrefutable pattern analogue).-  -- ^ Vector of the @(a, b)@ tuples that must be sorted in ascending order for the first argument. If there are several pairs (a, b) with the same @a@, +getBFst' +  :: (Ord a) => (b, V.Vector (a, b)) -- ^ @b@ is a default value that can be substituted if there is no correspendence in the set of @(a, b)@ tuples (the 'otherwise' or irrefutable pattern analogue).+  -- ^ Vector of the @(a, b)@ tuples that must be sorted in ascending order for the first argument. If there are several pairs @(a, b)@ with the same @a@,    -- ^ the function gives a resulting @b@ as if there is only the first one   -> a -- ^ an element for which the corresponding resulting b must be found   -> b -- ^ the result-getBFst' (def, vec) l | if (l < (fst (V.unsafeHead vec))) then True else (l > (fst (V.unsafeLast vec))) = def-                      | (V.length vec >= 2) = if l <= fst (vec V.! (V.length vec `quot` 2))+getBFst' (def, vec) l | if compare l (fst (V.unsafeIndex vec 0)) == LT then True else compare l (fst (V.unsafeIndex vec (V.length vec - 1))) == GT = def+                      | compare (V.length vec) 2 /= LT = if compare l (fst (V.unsafeIndex vec ((V.length vec `quot` 2) - 1))) /= GT   then getBFst' (def, (V.unsafeSlice 0 (V.length vec `quot` 2) vec)) l    else getBFst' (def, (V.unsafeSlice (V.length vec `quot` 2) (V.length vec - (V.length vec `quot` 2)) vec)) l -                      | otherwise = snd (V.unsafeHead vec)+                      | otherwise = snd (V.unsafeIndex vec 0)+{-# INLINE getBFst' #-}                     -- | The function that uses special realization of the binary search to effectively transform the @Vector a@ to @Vector b@ instead of simply use  --@@ -90,6 +92,7 @@   -> V.Vector a -- ^ a Vector needed to be transformed accordingly to the correct @(a, b)@ tuple pairs   -> V.Vector b -- ^ the resulting Vector getBFstV c y = V.map (getBFst' (y, c))+{-# INLINE getBFstV #-}  -- | The function that uses special kind of bisection to effectively transform the @[a]@ to @[b]@ instead of simply use  --@@ -120,13 +123,15 @@   -> [a] -- ^ a list of values needed to be transformed accordingly to the correct @(a, b)@ tuple pairs   -> [b] -- ^ the resulting list getBFst c y = map (getBFst' (y, c))+{-# INLINE getBFst #-}  -- | Function that sorts a list of @(a, b)@ tuples by the first argument  -- and is inspired by Data.List.sort function (the last one can be used for sorting the @(a, b)@ tuples where both the types of @a@ and @b@ -- have instances of the class Ord). It is inspired by the work: https://wiki.haskell.org/Introduction sortFst :: (Ord a) => [(a, b)] -> [(a, b)]-sortFst xs | not . null $ xs = let z = fst . head $ xs in sortFst (filter (\(x, _) -> x < z) xs) ++ filter (\(x, _) -> x == z) xs ++ sortFst (filter (\(x, _) -> x > z) xs)-           | otherwise = []+sortFst xs = if null xs then [] else sortFst (filter (\(x, _) -> compare x (fst (head xs)) == LT) xs) ++ filter (\(x, _) -> x == (fst (head xs))) xs ++ +  sortFst (filter (\(x, _) -> compare x (fst (head xs)) == GT) xs)+{-# INLINE sortFst #-}             -- | Function that prepares the list of @(a, b)@ tuples representing the  --@@ -142,13 +147,17 @@ -- -- The resulting vector has for every @a@ only one element, which was the first in the list of tuples @(a, b)@ after sorting by 'sortFst' function. ---sortFstV :: (Ord a) => [(a, b)] -> V.Vector (a, b)-sortFstV = V.fromList . L.nubBy (\x y -> fst x == fst y) . sortFst+sortFstV +  :: (Ord a) => [(a, b)] -- ^ The list of conditions that is then converted to the corresponding Vector+   -> V.Vector (a, b) -- ^ the resulting sorted Vector that can be used further in getBFst' and its successors.+sortFstV = V.fromList . L.nubBy (\(x, _) (y, _) -> x == y) . sortFst+{-# INLINE sortFstV #-}  -- | The function that is used to filter @[(a, b)]@ of the corresponding values for getFstB' to obtain the @Vector (a, b)@  -- such that the @b@ element for the sequence of pairs @(a, b)@ with the same @a@ is selected by the predicate @p@ and is not necessarily the first one  -- as it is for the getFstB' function and its successors by default.-filterP :: (Ord a) => ((a, b) -> Bool) -- ^ The predicate @p@ used to select the only one value of @b@ in the pairs @(a, b)@ with the same @a@. +filterP +  :: (Ord a) => ((a, b) -> Bool) -- ^ The predicate @p@ used to select the only one value of @b@ in the pairs @(a, b)@ with the same @a@.    -- ^ If there are several pairs @(a, b)@ for the same @a@ that satisfies a predicate then the first one is used. For large @[(a, b)]@    -- ^ it can be rather complex.   -> [(a, b)] -- ^ The list of @(a, b)@ sorted in the ascending order by the first element a (e. g. by the 'sortFst' function)@@ -158,4 +167,5 @@ -- -- > filterP (\(t, w) -> (t == "1") || (w > 'f')) . sortFst $ [("1",'a'),("4a",'k'),("4a",'b'),("4a",'c'),("4a",'d'),("4a",'e'),("b7",'c'),("b7",'k')] = [("1",'a'),("4a",'k'),("b7",'k')] -- -filterP p xs = V.fromList . concatMap (\x -> take 1 . dropWhile (not . p) $ x) $ L.groupBy (\(x1,_) (x2,_) -> x1 == x2) xs+filterP p xs = V.fromList . concatMap (\x -> take 1 . dropWhile (not . p) $ x) . L.groupBy (\(x1,_) (x2,_) -> x1 == x2) $ xs+{-# INLINE filterP #-}

@@ -18,4 +18,9 @@ * First version revised D. Some performance improvements and changing the documentation. The benchmark testing continues. +## 0.1.6.0 -- 2019-09-30++* First version revised E. Some performance improvements and changing the documentation.+The benchmark testing continues.+ 

@@ -2,7 +2,7 @@ -- see http://haskell.org/cabal/users-guide/  name:                mmsyn2-version:             0.1.5.0+version:             0.1.6.0 synopsis:            The library that can be used for multiple (Ord a) => a -> b transformations description:         The library that can be used for optimization or another representation of multiple (Ord a) => a -> b transformations homepage:            https://oleksandrzhabenko.github.io/mmsyn2@@ -20,7 +20,7 @@   exposed-modules:     CaseBi   -- other-modules:   -- other-extensions:-  build-depends:       base >=4.5 && <4.13, vector >=0.12 && <0.13+  build-depends:       base >=4.3 && <4.13, vector >=0.11 && <0.13   -- hs-source-dirs:   default-language:    Haskell2010   -- optimization:        2