mmsyn2 0.1.7.0 → 0.1.8.0

raw patch · 3 files changed

+51/−37 lines, 3 filesdep ~basedep ~vectorPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: base, vector

API changes (from Hackage documentation)

Files

• CaseBi.hs +44/−35
• ChangeLog.md +5/−0
• mmsyn2.cabal +2/−2

@@ -1,3 +1,12 @@+-- |+-- Module      :  CaseBi+-- Copyright   :  (c) OleksandrZhabenko 2019+-- License     :  MIT+-- Maintainer  :  olexandr543@yahoo.com+--+-- A library that can be used as a @case ... of@ constuction analogue for the multiple @Ord a => a -> b@ transformations and data representation.++ module CaseBi ( -- * Function that can be used instead of @case ... of@ construction --@@ -19,8 +28,6 @@  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)  -- | The function that can be used instead of the 'case ... of' function --@@ -32,16 +39,17 @@ -- >   an -> bn -- >   _  -> 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 (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 --- the following functions 'sortFst' and 'sortFstV'. +-- 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 (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 'V.Vector' @(a, b)@ as somewhat like a complicated filter or like a special sieve. The 'V.Vector' @(a, b)@ must be +-- sorted in ascending order here for the algorithm to be used correctly. For this you can use the following functions 'sortFst' and 'sortFstV'.  -- --- @b@ before @Vector (a, b)@ in the tuple in the type definition of the 'getBFst' must be a @defaultValue@ for 'case' above. +-- @b@ before 'V.Vector' @(a, b)@ in the tuple in the type definition of the 'getBFst' must be a @defaultValue@ for 'case' above.  ----- @Vector (a, b)@ corresponds to +-- 'V.Vector' @(a, b)@ corresponds to  -- -- >  a1 -> b1 -- >  a2 -> b2@@ -52,16 +60,17 @@ 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+  -> a -- ^ an element for which the corresponding resulting @b@ must be found   -> b -- ^ the result-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.unsafeIndex vec 0)+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.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 +-- | The function that uses special realization of the binary search to effectively transform the 'V.Vector' @a@ to 'V.Vector' @b@ instead of simply use  -- -- > case var of -- >   a1 -> b1@@ -71,12 +80,12 @@ -- >   an -> bn -- >   _  -> defaultValue -- --- The @Vector (a, b)@ must be sorted in ascending order here for the algorithm to be used correctly. For this you can use +-- The 'V.Vector' @(a, b)@ must be sorted in ascending order here for the algorithm to be used correctly. For this you can use  -- the following functions 'sortFst' and 'sortFstV'. it can be used to simplify the procedure for optimizing the code for transformation of the Vector data. -- --- @b@ after @Vector (a, b)@ in the type definition of the 'getBFstV' must be a @defaultValue@ for 'case' above. +-- @b@ after 'V.Vector' @(a, b)@ in the type definition of the 'getBFstV' must be a @defaultValue@ for @case ... of@ above.  ----- @Vector (a, b)@ corresponds to +-- 'V.Vector' @(a, b)@ corresponds to  -- -- >  a1 -> b1 -- >  a2 -> b2@@ -84,10 +93,10 @@ -- >  ... -- >  an -> bn -- -getBFstV :: (Ord a) => V.Vector (a, b) -- ^ Vector of the @(a, b)@ tuples that are sorted in ascending order for the first argument+getBFstV :: (Ord a) => V.Vector (a, b) -- ^ 'V.Vector' of the @(a, b)@ tuples that are sorted in ascending order for the first argument   -> 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)-  -> V.Vector a -- ^ a Vector needed to be transformed accordingly to the correct @(a, b)@ tuple pairs-  -> V.Vector b -- ^ the resulting Vector+  -> V.Vector a -- ^ a 'V.Vector' needed to be transformed accordingly to the correct @(a, b)@ tuple pairs+  -> V.Vector b -- ^ the resulting 'V.Vector' getBFstV c y = V.map (getBFst' (y, c)) {-# INLINE getBFstV #-} @@ -101,13 +110,13 @@ -- >   an -> bn -- >   _  -> defaultValue -- --- The @Vector (a, b)@ must be sorted in ascending order here for the algorithm to be used correctly. For this you can use --- the following functions 'sortFst' and 'sortFstV'. The function can be used to simplify the procedure for optimizing the code for transformation of the list data --- or to represent the data in another way.+-- A 'V.Vector' @(a, b)@ must be sorted in ascending order here for the algorithm to be used correctly. For this you can use +-- the following functions 'sortFst' and 'sortFstV'. The function can be used to simplify the procedure for optimizing the code +-- for transformation of the list data or to represent the data in another way. -- --- @b@ after @Vector (a, b)@ in the type definition of the 'getBFst' must be a @defaultValue@ for 'case' above. +-- @b@ after the 'V.Vector' @(a, b)@ in the type definition of the 'getBFst' must be a @defaultValue@ for @case ... of@ above.  ----- @Vector (a, b)@ corresponds to +-- 'V.Vector' @(a, b)@ corresponds to  -- -- >  a1 -> b1 -- >  a2 -> b2@@ -115,7 +124,7 @@ -- >  ... -- >  an -> bn -- -getBFst :: (Ord a) => V.Vector (a, b) -- ^ Vector of the @(a, b)@ tuples that must be sorted in ascending order for the first argument+getBFst :: (Ord a) => V.Vector (a, b) -- ^ 'V.Vector' of the @(a, b)@ tuples that must be sorted in ascending order for the first argument   -> 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)   -> [a] -- ^ a list of values needed to be transformed accordingly to the correct @(a, b)@ tuple pairs   -> [b] -- ^ the resulting list@@ -123,8 +132,8 @@ {-# 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+-- 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 = 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)@@ -142,17 +151,17 @@ -- -- for usage in the 'getBFst' and 'getBFstV' functions.  ----- 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.+-- The resulting 'V.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)] -- ^ 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.+   -> 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)@ +-- | Is used to filter @[(a, b)]@ of the corresponding values for 'getFstB'' to obtain the 'V.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.+-- 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@.    -- ^ 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)]@ 

@@ -31,3 +31,8 @@ ## 0.1.7.0 -- 2019-12-24  * First version revised G. Changed the dependency bounds so that it now can be compiled with GHC 8.8.1.++## 0.1.8.0 -- 2020-05-14++* First version revised H. Changed the dependency bounds so that it now can be compiled with GHC 8.10* series. Some documentation improvements.+

@@ -2,7 +2,7 @@ -- see http://haskell.org/cabal/users-guide/  name:                mmsyn2-version:             0.1.7.0+version:             0.1.8.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.3 && <4.14, vector >=0.11 && <0.13+  build-depends:       base >=4.3 && <4.15, vector >=0.11 && <0.14   -- hs-source-dirs:   default-language:    Haskell2010   -- optimization:        2