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 |

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)
- linearSearch :: Ord k => Vector (k, v) -> k -> Maybe v
- linearSearchR :: Ord k => Vector (k, v) -> k -> Maybe v
- binarySearch :: Ord k => Vector (k, v) -> k -> Either Int Int

# FlatMap backed by sorted vector

#### Instances

Functor (FlatMap k) Source # | |

Foldable (FlatMap k) Source # | |

Defined in Z.Data.Vector.FlatMap 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] # 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 # | |

Traversable (FlatMap k) Source # | |

(Eq k, Eq v) => Eq (FlatMap k v) Source # | |

(Ord k, Ord v) => Ord (FlatMap k v) Source # | |

Defined in Z.Data.Vector.FlatMap | |

(Show k, Show v) => Show (FlatMap k v) Source # | |

Ord k => Semigroup (FlatMap k v) Source # | |

Ord k => Monoid (FlatMap k v) Source # | |

(Ord k, Arbitrary k, Arbitrary v) => Arbitrary (FlatMap k v) Source # | |

(CoArbitrary k, CoArbitrary v) => CoArbitrary (FlatMap k v) Source # | |

Defined in Z.Data.Vector.FlatMap coarbitrary :: FlatMap k v -> Gen b -> Gen b # | |

(NFData k, NFData v) => NFData (FlatMap k v) Source # | |

Defined in Z.Data.Vector.FlatMap | |

(Print k, Print v) => Print (FlatMap k v) Source # | |

Defined in Z.Data.Vector.FlatMap | |

JSON a => JSON (FlatMap Text a) Source # | default instance prefer later key |

sortedKeyValues :: FlatMap k v -> Vector (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.

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

That is, behaves exactly like a regular `traverseWithKey`

f s == `pack`

<$> `traverse`

((k, v) -> (,) k <$> f k v) (`unpack`

m)`traverse`

except that the traversing
function also has access to the key associated with a value.

# search on vectors

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

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