Safe Haskell | None |
---|---|

Language | Haskell2010 |

## 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

:: Ord a | |

=> b | a default value that can be substituted if there is no correspendence in the set of (a, b) tuples (the |

-> Vector (a, b) | Vector of the (a, b) tuples that are sorted in ascending order for the first argument. If there are several pairs (a, b) with the same a, the function acts as if there is only the first one |

-> a | an element for which the corresponding resulting b must be found |

-> 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

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 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

:: Ord a | |

=> 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 |

-> [a] | a list of values needed to be transformed accordingly to the correct (a, b) tuple pairs |

-> [b] | the resulting list |

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

:: Ord a | |

=> 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 |

-> Vector a | a Vector needed to be transformed accordingly to the correct (a, b) tuple pairs |

-> Vector b | the resulting Vector |

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

# Additional functions that are used to sort a list of pairs (which can be obtained by e. g. Prelude.zip

sortFst :: Ord a => [(a, b)] -> [(a, b)] Source #

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).

## Function that can be used for changing the Vector (a, b) during its creation

:: 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 |

-> 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')] |

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.