Copyright	(c) Dong Han 2017-2019 (c) Tao He 2018-2019
License	BSD
Maintainer	winterland1989@gmail.com
Stability	experimental
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Z.Data.Vector.FlatMap

Contents

FlatMap backed by sorted vector
fold and traverse
binary & linear search on vectors

Description

This module provides a simple key value map based on sorted vector and binary search. It's particularly suitable for small sized key value collections such as deserializing intermediate representation. But can also used in various place where insertion and deletion is rare but require fast lookup.

Synopsis

data FlatMap k v
sortedKeyValues :: FlatMap k v -> Vector (k, v)
size :: FlatMap k v -> Int
null :: FlatMap k v -> Bool
empty :: FlatMap k v
map' :: (v -> v') -> FlatMap k v -> FlatMap k v'
kmap' :: (k -> v -> v') -> FlatMap k v -> FlatMap k v'
pack :: Ord k => [(k, v)] -> FlatMap k v
packN :: Ord k => Int -> [(k, v)] -> FlatMap k v
packR :: Ord k => [(k, v)] -> FlatMap k v
packRN :: Ord k => Int -> [(k, v)] -> FlatMap k v
unpack :: FlatMap k v -> [(k, v)]
unpackR :: FlatMap k v -> [(k, v)]
packVector :: Ord k => Vector (k, v) -> FlatMap k v
packVectorR :: Ord k => Vector (k, v) -> FlatMap k v
lookup :: Ord k => k -> FlatMap k v -> Maybe v
delete :: Ord k => k -> FlatMap k v -> FlatMap k v
insert :: Ord k => k -> v -> FlatMap k v -> FlatMap k v
adjust' :: Ord k => (v -> v) -> k -> FlatMap k v -> FlatMap k v
merge :: forall k v. Ord k => FlatMap k v -> FlatMap k v -> FlatMap k v
mergeWithKey' :: forall k v. Ord k => (k -> v -> v -> v) -> FlatMap k v -> FlatMap k v -> FlatMap k v
foldrWithKey :: (k -> v -> a -> a) -> a -> FlatMap k v -> a
foldrWithKey' :: (k -> v -> a -> a) -> a -> FlatMap k v -> a
foldlWithKey :: (a -> k -> v -> a) -> a -> FlatMap k v -> a
foldlWithKey' :: (a -> k -> v -> a) -> a -> FlatMap k v -> a
traverseWithKey :: Applicative t => (k -> a -> t b) -> FlatMap k a -> t (FlatMap k b)
binarySearch :: Ord k => Vector (k, v) -> k -> Either Int Int
linearSearch :: Ord k => Vector (k, v) -> k -> Maybe v
linearSearchR :: Ord k => Vector (k, v) -> k -> Maybe v

FlatMap backed by sorted vector

data FlatMap k v Source #

Instances

Instances details

Functor (FlatMap k) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods fmap :: (a -> b) -> FlatMap k a -> FlatMap k b # (<$) :: a -> FlatMap k b -> FlatMap k a #
Foldable (FlatMap k) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods fold :: Monoid m => FlatMap k m -> m # foldMap :: Monoid m => (a -> m) -> FlatMap k a -> m # foldMap' :: Monoid m => (a -> m) -> FlatMap k a -> m # foldr :: (a -> b -> b) -> b -> FlatMap k a -> b # foldr' :: (a -> b -> b) -> b -> FlatMap k a -> b # foldl :: (b -> a -> b) -> b -> FlatMap k a -> b # foldl' :: (b -> a -> b) -> b -> FlatMap k a -> b # foldr1 :: (a -> a -> a) -> FlatMap k a -> a # foldl1 :: (a -> a -> a) -> FlatMap k a -> a # toList :: FlatMap k a -> [a] # null :: FlatMap k a -> Bool # length :: FlatMap k a -> Int # elem :: Eq a => a -> FlatMap k a -> Bool # maximum :: Ord a => FlatMap k a -> a # minimum :: Ord a => FlatMap k a -> a # sum :: Num a => FlatMap k a -> a # product :: Num a => FlatMap k a -> a #
Traversable (FlatMap k) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods traverse :: Applicative f => (a -> f b) -> FlatMap k a -> f (FlatMap k b) # sequenceA :: Applicative f => FlatMap k (f a) -> f (FlatMap k a) # mapM :: Monad m => (a -> m b) -> FlatMap k a -> m (FlatMap k b) # sequence :: Monad m => FlatMap k (m a) -> m (FlatMap k a) #
(Eq k, Eq v) => Eq (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods (==) :: FlatMap k v -> FlatMap k v -> Bool # (/=) :: FlatMap k v -> FlatMap k v -> Bool #
(Ord k, Ord v) => Ord (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods compare :: FlatMap k v -> FlatMap k v -> Ordering # (<) :: FlatMap k v -> FlatMap k v -> Bool # (<=) :: FlatMap k v -> FlatMap k v -> Bool # (>) :: FlatMap k v -> FlatMap k v -> Bool # (>=) :: FlatMap k v -> FlatMap k v -> Bool # max :: FlatMap k v -> FlatMap k v -> FlatMap k v # min :: FlatMap k v -> FlatMap k v -> FlatMap k v #
(Show k, Show v) => Show (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods showsPrec :: Int -> FlatMap k v -> ShowS # show :: FlatMap k v -> String # showList :: [FlatMap k v] -> ShowS #
Ord k => Semigroup (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods (<>) :: FlatMap k v -> FlatMap k v -> FlatMap k v # sconcat :: NonEmpty (FlatMap k v) -> FlatMap k v # stimes :: Integral b => b -> FlatMap k v -> FlatMap k v #
Ord k => Monoid (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods mempty :: FlatMap k v # mappend :: FlatMap k v -> FlatMap k v -> FlatMap k v # mconcat :: [FlatMap k v] -> FlatMap k v #
(NFData k, NFData v) => NFData (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods rnf :: FlatMap k v -> () #
(Ord k, Arbitrary k, Arbitrary v) => Arbitrary (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods arbitrary :: Gen (FlatMap k v) shrink :: FlatMap k v -> [FlatMap k v]
(CoArbitrary k, CoArbitrary v) => CoArbitrary (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods coarbitrary :: FlatMap k v -> Gen b -> Gen b
(ToText k, ToText v) => ToText (FlatMap k v) Source #
Instance details Defined in Z.Data.Vector.FlatMap Methods toTextBuilder :: Int -> FlatMap k v -> TextBuilder () Source #
FromValue a => FromValue (FlatMap Text a) Source #	default instance prefer later key
Instance details Defined in Z.Data.JSON.Base Methods fromValue :: Value -> Converter (FlatMap Text a) Source #
EncodeJSON a => EncodeJSON (FlatMap Text a) Source #
Instance details Defined in Z.Data.JSON.Base Methods encodeJSON :: FlatMap Text a -> Builder () Source #
ToValue a => ToValue (FlatMap Text a) Source #
Instance details Defined in Z.Data.JSON.Base Methods toValue :: FlatMap Text a -> Value Source #

sortedKeyValues :: FlatMap k v -> Vector (k, v) Source #

size :: FlatMap k v -> Int Source #

null :: FlatMap k v -> Bool Source #

empty :: FlatMap k v Source #

O(1) empty flat map.

map' :: (v -> v') -> FlatMap k v -> FlatMap k v' Source #

kmap' :: (k -> v -> v') -> FlatMap k v -> FlatMap k v' Source #

pack :: Ord k => [(k, v)] -> FlatMap k v Source #

O(N*logN) Pack list of key values, on key duplication prefer left one.

packN :: Ord k => Int -> [(k, v)] -> FlatMap k v Source #

O(N*logN) Pack list of key values with suggested size, on key duplication prefer left one.

packR :: Ord k => [(k, v)] -> FlatMap k v Source #

O(N*logN) Pack list of key values, on key duplication prefer right one.

packRN :: Ord k => Int -> [(k, v)] -> FlatMap k v Source #

O(N*logN) Pack list of key values with suggested size, on key duplication prefer right one.

unpack :: FlatMap k v -> [(k, v)] Source #

O(N) Unpack key value pairs to a list sorted by keys in ascending order.

This function works with foldr/build fusion in base.

unpackR :: FlatMap k v -> [(k, v)] Source #

O(N) Unpack key value pairs to a list sorted by keys in descending order.

This function works with foldr/build fusion in base.

packVector :: Ord k => Vector (k, v) -> FlatMap k v Source #

O(N*logN) Pack vector of key values, on key duplication prefer left one.

packVectorR :: Ord k => Vector (k, v) -> FlatMap k v Source #

O(N*logN) Pack vector of key values, on key duplication prefer right one.

lookup :: Ord k => k -> FlatMap k v -> Maybe v Source #

O(logN) Binary search on flat map.

delete :: Ord k => k -> FlatMap k v -> FlatMap k v Source #

O(N) Delete a key value pair by key.

insert :: Ord k => k -> v -> FlatMap k v -> FlatMap k v Source #

O(N) Insert new key value into map, replace old one if key exists.

adjust' :: Ord k => (v -> v) -> k -> FlatMap k v -> FlatMap k v Source #

O(N) Modify a value by key.

The value is evaluated to WHNF before writing into map.

merge :: forall k v. Ord k => FlatMap k v -> FlatMap k v -> FlatMap k v Source #

O(n+m) Merge two FlatMap, prefer right value on key duplication.

mergeWithKey' :: forall k v. Ord k => (k -> v -> v -> v) -> FlatMap k v -> FlatMap k v -> FlatMap k v Source #

O(n+m) Merge two FlatMap with a merge function.

fold and traverse

foldrWithKey :: (k -> v -> a -> a) -> a -> FlatMap k v -> a Source #

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

During folding k is in descending order.

foldrWithKey' :: (k -> v -> a -> a) -> a -> FlatMap k v -> a Source #

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

During folding k is in descending order.

foldlWithKey :: (a -> k -> v -> a) -> a -> FlatMap k v -> a Source #

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

During folding k is in ascending order.

foldlWithKey' :: (a -> k -> v -> a) -> a -> FlatMap k v -> a Source #

O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).

During folding k is in ascending order.

traverseWithKey :: Applicative t => (k -> a -> t b) -> FlatMap k a -> t (FlatMap k b) Source #

O(n). traverseWithKey f s == pack $ traverse ((k, v) -> (,) k $ f k v) (unpack m) That is, behaves exactly like a regular traverse except that the traversing function also has access to the key associated with a value.

binary & linear search on vectors

binarySearch :: Ord k => Vector (k, v) -> k -> Either Int Int Source #

Find the key's index in the vector slice, if key exists return Right, otherwise Left, i.e. the insert index

This function only works on ascending sorted vectors.

linearSearch :: Ord k => Vector (k, v) -> k -> Maybe v Source #

linear scan search from left to right, return the first one if exist.

linearSearchR :: Ord k => Vector (k, v) -> k -> Maybe v Source #

linear scan search from right to left, return the first one if exist.