Copyright  (c) OleksandrZhabenko 20192021 

License  MIT 
Maintainer  olexandr543@yahoo.com 
Stability  Experimental 
Safe Haskell  None 
Language  Haskell2010 
A library that can be used as a case ... of
constuction analogue for the multiple Ord a => a > b
transformations and data representation.
Synopsis
 getBFst' :: Ord a => (b, Vector (a, b)) > a > b
 getBFst :: Ord a => Vector (a, b) > b > [a] > [b]
 getBFstV :: Ord a => Vector (a, b) > b > Vector a > Vector b
 sortFst :: Ord a => [(a, b)] > [(a, b)]
 sortFstV :: Ord a => [(a, b)] > Vector (a, b)
 filterP :: Ord a => ((a, b) > Bool) > [(a, b)] > Vector (a, b)
Function that can be used instead of case ... of
construction
:: Ord a  
=> (b, Vector (a, b)) 

> a  an element for which the corresponding resulting 
> b  the result 
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 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
.
b
before 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
a1 > b1 a2 > b2 a3 > b3 ... an > bn
:: Ord a  
=> Vector (a, b) 

> b  a default value that can be substituted if there is no correspendence in the set of 
> [a]  a list of values needed to be transformed accordingly to the correct 
> [b]  the resulting list 
The function that uses special kind of bisection to effectively transform the [a]
to [b]
instead of simply use
case var of a1 > b1 a2 > b2 a3 > b3 ... an > bn _ > defaultValue
A 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 the Vector
(a, b)
in the type definition of the getBFst
must be a defaultValue
for case ... of
above.
Vector
(a, b)
corresponds to
a1 > b1 a2 > b2 a3 > b3 ... an > bn
:: Ord a  
=> Vector (a, b) 

> b  a default value that can be substituted if there is no correspendence in the set of 
> Vector a  a 
> Vector b  the resulting 
The function that uses special realization of the binary search to effectively transform the Vector
a
to Vector
b
instead of simply use
case var of a1 > b1 a2 > b2 a3 > b3 ... 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
. 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 ... of
above.
Vector
(a, b)
corresponds to
a1 > b1 a2 > b2 a3 > b3 ... an > bn
Additional functions that are used to sort a list of pairs (which can be obtained e. g. by zip
)
sortFst :: Ord a => [(a, b)] > [(a, b)] Source #
Function that sorts a list of (a, b)
tuples by the first argument
and is inspired by 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
:: Ord a  
=> [(a, b)]  The list of conditions that is then converted to the corresponding Vector 
> Vector (a, b)  the resulting sorted Vector that can be used further in 
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.
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.
Function that can be used for changing the Vector (a, b)
during its creation
:: Ord a  
=> ((a, b) > Bool)  The predicate 
> [(a, b)]  The list of 
> Vector (a, b)  The resulting filtered 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')] 
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.