mmsyn2-array (empty) → 0.1.0.0

raw patch · 5 files changed

+195/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

• CHANGELOG.md +5/−0
• CaseBi/Arr.hs +143/−0
• LICENSE +20/−0
• Setup.hs +2/−0
• mmsyn2-array.cabal +25/−0

@@ -0,0 +1,5 @@+# Revision history for mmsyn2-array++## 0.1.0.0 -- 2020-12-14++* First version. Released on an unsuspecting world.

@@ -0,0 +1,143 @@+{-# OPTIONS_HADDOCK show-extensions #-}+{-# LANGUAGE UnboxedTuples #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE FlexibleContexts #-}++-- | Module    :  CaseBi.Arr+-- Copyright   :  (c) OleksandrZhabenko 2019+-- License     :  MIT+-- Stability   :  Experimental+-- 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. Uses 'Array' internally. If you use the module in GHCi, then, please,+-- run the interpreter with the flag -fobject-code.+--++module CaseBi.Arr (+{- |  * Functions that can be used instead of @case ... of@ construction+@+case var of+ a1 -> b1+ a2 -> b2+ a3 -> b3+ ...+ an -> bn+ _  -> def+@+for efficiency or other data representation+-}+  -- * Basic functions+  getBFst''+  , getBFst'+  -- * With a transformation to the array+  , listArrSortedByFst+  , getBFstLSorted'+  , getBFstL'+) where++import qualified Data.List as L (sortBy)+import GHC.Arr+import Data.Ord (comparing)++{- | The function that can be used instead of the 'case ... of' function+@+case var of+ a1 -> b1+ a2 -> b2+ a3 -> b3+ ...+ 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 an 'Array' of @(a, b)@ as somewhat like a complicated filter or like a special sieve. The array must be sorted in ascending order here for the algorithm to be used correctly. For this you can use the function 'listArrSortedBy' or the similar ones.+The function 'getBFst''' is used internally in the 'getBFst'' that is recommended to be used in most cases. Nevertheless,+it is provided here if you have precomputed the first two arguments or at least some parts of them so that+you can reduce the needed amount of computations in the 'getBFst''.+-}+getBFst''+  :: Ord a => (# Int, (a, b) #) -- ^ The first unboxed tuple of the index and the element of the array.+  -> (# Int, (a, b) #) -- ^ The second unboxed tuple of the index and the element of the array.+  -> Array i (a, b) -- ^ The array of the pairs of the compared value and the result that is used in case the last argument is equal to the compared value.+  -> b -- ^ The default value that is used if no first element in the array tuples equals to the compared value.+  -> a -- ^ The compared value, well, the @main@ function argument, to which it is applied.+  -> b -- ^ The resulting branch value.+getBFst'' (# i, k #) (# j, m #) arr def x+ | x > fst k && x < fst m = gBF3 (# i, k #) (# j, m #) arr def x+ | otherwise = def+{-# INLINE getBFst'' #-}++-- | The meaning of the arguments is the same as for 'getBFst'''. Is used internally in it.+gBF3 :: Ord a => (# Int, (a, b) #) -> (# Int, (a, b) #) -> Array i (a, b) -> b -> a -> b+gBF3 (# i, k #) (# j, m #) arr def x+ | j - i > 1 = let !n = (i + j) `quot` 2 in let !p = unsafeAt arr n in+    case compare x (fst p) of+     GT -> gBF3 (# n, p #) (# j, m #) arr def x+     EQ -> snd p+     _  -> gBF3 (# i, k #) (# n, p #) arr def x+ | x == fst m = snd m+ | x == fst k = snd k+ | otherwise = def+{-# INLINABLE gBF3 #-}++-- | A generally written without extending variant of the 'getBFst'''.+getBFst' :: Ord a => (b, Array Int (a, b)) -> a -> b+getBFst' (def, arr) = getBFst'' (# i, k #) (# j, m #) arr def+  where (!i,!j) = bounds arr+        !k = unsafeAt arr i+        !m = unsafeAt arr j+{-# INLINE getBFst' #-}++{- | If the list argument is sorted in the ascending order by the first element in every tuple, then to reduce+computations instead of+@+\def xs x -> getBFst' (def, listArray (0,length xs - 1) xs) x+@+you can use this function.+-}+getBFstLSorted'+  :: Ord a => b+  -> [(a, b)]+  -> a+  -> b+getBFstLSorted' def xs = getBFst'' (# 0, k #) (# l, m #) arr def+  where !l = length xs - 1+        !arr = listArray (0,l) xs+        !k = unsafeAt arr 0+        !m = unsafeAt arr l+{-# INLINE getBFstLSorted' #-}++{- | If it is unknown whether the list argument is sorted in the ascending order by the first element in every+tuple (or, definitely, it is not, speaking generally), then instead of+@+\def xs x -> getBFst' (def, listArray (0,length xs - 1) . sortBy (comparing fst) $ xs) x+@+you can use this function.+-}+getBFstL'+  :: Ord a => b+  -> [(a, b)]+  -> a+  -> b+getBFstL' def xs = getBFst'' (# 0, k #) (# l, m #) arr def+  where !l = length xs - 1+        !arr = listArray (0,l) . L.sortBy (comparing fst) $ xs+        !k = unsafeAt arr 0+        !m = unsafeAt arr l+{-# INLINE getBFstL' #-}++{- | Sorts the list of pairs by the first element in the tuples, then transforms them into an immutable array. Can be+used only if the list contains no more than 2^31 - 1 elements though this is not checked, it is up to user+to check this constraint before or provide its correctness by design.+-}+listArrSortedByFst :: Ord a => [(a,b)] -> Array Int (a,b)+listArrSortedByFst xs = listArray (0,l - 1) ys+  where !ys = L.sortBy (comparing fst) xs+        !l = length ys+{-# INLINE listArrSortedByFst #-}

@@ -0,0 +1,20 @@+Copyright (c) 2020 OleksandrZhabenko++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,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,25 @@+-- Initial mmsyn2-array.cabal generated by cabal init.  For further+-- documentation, see http://haskell.org/cabal/users-guide/++name:                mmsyn2-array+version:             0.1.0.0+synopsis:            A library with less dependencies that can be used for multiple @Ord a => a -> b@ transformations.+description:         A library that can be used as a @case ... of@ constuction analogue for the multiple @Ord a => a -> b@ transformations and data representation. Uses "GHC.Arr" internally. If you use the module in GHCi, then, please, run the interpreter with the flag -fobject-code.+homepage:            https://hackage.haskell.org/package/mmsyn2-array+license:             MIT+license-file:        LICENSE+author:              OleksandrZhabenko+maintainer:          olexandr543@yahoo.com+copyright:           Oleksandr Zhabenko+category:            Development, Data, Language+build-type:          Simple+extra-source-files:  CHANGELOG.md+cabal-version:       >=1.10++library+  exposed-modules:     CaseBi.Arr+  -- other-modules:+  other-extensions:    UnboxedTuples, BangPatterns, FlexibleContexts+  build-depends:       base >=4.7 && <4.15+  -- hs-source-dirs:+  default-language:    Haskell2010