mmsyn2 (empty) → 0.1.2.0

raw patch · 6 files changed

+242/−0 lines, 6 filesdep +basedep +vectorsetup-changed

Dependencies added: base, vector

Files

• CaseBi.hs +182/−0
• ChangeLog.md +6/−0
• LICENSE +21/−0
• README.md +4/−0
• Setup.hs +2/−0
• mmsyn2.cabal +27/−0

@@ -0,0 +1,182 @@+{-# LANGUAGE BangPatterns #-}++module CaseBi (+-- * Function that can be used instead of +--+-- > case var of +-- >   a1 -> b1+-- >   a2 -> b2+-- >   a3 -> b3+-- >   ...+-- >   an -> bn+-- >   _  -> def+-- +-- for efficiency+  getBFst', getBFst, getBFstV, +-- * Additional functions that are used to sort a list of pairs (which can be obtained by e. g. Prelude.zip)+  sortFst, sortFstV,+-- ** Function that can be used for changing the Vector (a, b) during its creation +  filterP+) where++import qualified Data.Vector as V (Vector,head,last,take,drop,length,(!),fromList,map)+import qualified Data.List as L (groupBy)+import Prelude+-- (Bool,Eq,Ord,map,(>=),(<=),(>),(<),(==),(&&),(.),(++),(-),($),filter,otherwise,fst,snd,div,not,null,dropWhile,concatMap,take,seq,undefined)++-- | The function that can be used instead of the 'case ... of' function+--+-- > case var of+-- >   a1 -> b1+-- >   a2 -> b2+-- >   a3 -> b3+-- >   ...+-- >   an -> bn+-- >   _  -> defaultValue+-- +-- The function 'case a of ...' gives the /O(n)/ coplexity of the transformation of a to b here, +-- but the function getBFst' tries to give about /O(log n)/ complexity +-- The Vector v (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 type definition of the 'getBFst' must be a @defaultValue@ for 'case' above. +--+-- Vector (a, b) corresponds to +--+-- >  a1 -> b1+-- >  a2 -> b2+-- >  a3 -> b3+-- >  ...+-- >  an -> bn+-- +getBFst' :: (Ord 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)+  -> V.Vector (a, b) -- ^ 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 | (l < vElem0 vec) || (l > vElemL vec) = def+                   | (vIL vec >= 3) = if l <= fst (vec V.! (vIL vec `div` 2))+  then getBFst' def v1 l +  else getBFst' def v2 l+                   | (vIL vec == 2) = if l == vElem0 vec+  then snd . V.head $ vec+  else if l == vElem1 vec+         then snd $ vec V.! 1+         else if l == vElemL vec+                then snd . V.last $ vec+                else def+                   | (vIL vec == 1) = if l == vElem0 vec+  then snd . V.head $ vec+  else if l == vElemL vec+         then snd . V.last $ vec+         else def+                   | (vIL vec == 0) = snd . V.head $ vec+                   | otherwise = def+            where vElem0 = fst . V.head+                  vElem1 v = fst $ v V.! 1+                  vElemL = fst . V.last+                  vIL v = V.length v - 1+                  v1  = V.take (V.length vec `div` 2) vec+                  v2 = V.drop (V.length vec `div` 2) vec++-- | The function that uses special kind of bisection to effectively transform the Vector a to Vector b with  instead of simply use +--+-- > case var of+-- >   a1 -> b1+-- >   a2 -> b2+-- >   a3 -> b3+-- >   ...+-- >   an -> bn+-- >   _  -> defaultValue+-- +-- The function 'V.map (f (case var of ...)) [a]' gives the /O(n*m)/ coplexity of the transformation of Vector a to Vector b here +-- where m is the length of the Vector a (and Vector b respectively here), but the function 'getBFstV' tries to give about /O(m*log n)/ complexity +-- 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 m >> n than the function gives more efficiency. Even otherwise, +-- 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. +--+-- Vector (a, b) corresponds to +--+-- >  a1 -> b1+-- >  a2 -> b2+-- >  a3 -> b3+-- >  ...+-- >  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+  -> 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+getBFstV c y = V.map (getBFst' y c)++-- | The function that uses special kind of bisection to effectively transform the [a] to [b] with  instead of simply use +--+-- > case var of+-- >   a1 -> b1+-- >   a2 -> b2+-- >   a3 -> b3+-- >   ...+-- >   an -> bn+-- >   _  -> defaultValue+-- +-- The function 'map (f (case var of ...)) [a]' gives the /O(n*m)/ coplexity of the transformation of [a] to [b] here +-- where m is the length of the [a] (and [b] respectively here), but the function 'getBFst' tries to give about /O(m*log n)/ complexity +-- 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 m >> n than the function gives more efficiency. Even otherwise, +-- it can be used to simplify the procedure for optimizing the code for transformation of the list data.+-- +-- b after Vector (a, b) in the type definition of the 'getBFst' must be a defaultValue for 'case' above. +--+-- Vector (a, b) corresponds to +--+-- >  a1 -> b1+-- >  a2 -> b2+-- >  a3 -> b3+-- >  ...+-- >  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+  -> 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+getBFst c y = map (getBFst' y c)++-- | Function that sorts a list of (a, b) tuples by the first argument (@a@ must be an instance of class Ord)+-- 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 = []++-- | Function that prepares the list of (a, b) tuples representing the +--+-- > case var of +-- >   a1 -> b1+-- >   a2 -> b2+-- >   a3 -> b3+-- >    ...+-- >   an -> bn+-- >   _  -> defaultValue+--+-- for usage in the 'getBFst' and 'getBFstV' functions. @a@ must be an instance of class Ord.+--+sortFstV :: (Ord a) => [(a, b)] -> V.Vector (a, b)+sortFstV = V.fromList . sortFst++-- | The function that is used to filter a list [(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. +  -- ^ 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)+  -> V.Vector (a, b) -- ^ The resulting filtered Vector (a, b) that can be used for getFstB' and its successor functions+--+-- Example: +--+-- > 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+  +  

@@ -0,0 +1,6 @@+# Revision history for mmsyn2++## 0.1.2.0 -- 2019-09-24++* First version revised. From deprecated mm2. Some optimization changes.+

@@ -0,0 +1,21 @@+MIT License++Copyright (c) 2019 Oleksandr Zhabenko++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.

@@ -0,0 +1,4 @@+## Welcome to mmsyn2 home page!++mmsyn2 is the library that can be used for optimization of multiple (Ord a) => a -> b transformations.+

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,27 @@+-- Initial mm2.cabal generated by cabal init.  For further documentation,+-- see http://haskell.org/cabal/users-guide/++name:                mmsyn2+version:             0.1.2.0+synopsis:            The library that can be used for optimization of multiple (Ord a) => a -> b transformations+description:         The library that can be used for optimization of multiple (Ord a) => a -> b transformations+homepage:            https://oleksandrzhabenko.github.io/mmsyn2+license:             MIT+license-file:        LICENSE+author:              OleksandrZhabenko+maintainer:          olexandr543@yahoo.com+-- copyright:+category:            Development+build-type:          Simple+extra-source-files:  ChangeLog.md README.md+cabal-version:       >=1.10++library+  exposed-modules:     CaseBi+  -- other-modules:+  -- other-extensions:+  build-depends:       base >=4.10 && <=4.12, vector >=0.12 && <=0.13+  -- hs-source-dirs:+  default-language:    Haskell2010+  -- optimization:        2+  ghc-options:         -Odph