Safe Haskell	Safe
Language	Haskell2010

GraphQL.Internal.OrderedMap

Contents

Construction
Querying
Filtering
Combine
- Union
Conversion
Properties

Description

Data structure for mapping keys to values while preserving order of appearance.

There are many cases in GraphQL where we want to have a map from names to values, where values can easily be lookup up by name and name is unique. This would normally be modelled as a Map. However, in many of these cases, the order in which the entries appear matters.

That is,

{
  foo: 1,
  bar: 2
}

Is different to,

@ { bar: 2, foo: 1, }

Even though they have exactly the same keys, and the keys have exactly the same values.

Goal for this module is to provide data structures that are "complete enough" for implementing the rest of GraphQL.

Synopsis

Documentation

data OrderedMap key value Source #

Instances

Functor (OrderedMap key) Source #
Methods fmap :: (a -> b) -> OrderedMap key a -> OrderedMap key b # (<$) :: a -> OrderedMap key b -> OrderedMap key a #
Foldable (OrderedMap key) Source #
Methods fold :: Monoid m => OrderedMap key m -> m # foldMap :: Monoid m => (a -> m) -> OrderedMap key a -> m # foldr :: (a -> b -> b) -> b -> OrderedMap key a -> b # foldr' :: (a -> b -> b) -> b -> OrderedMap key a -> b # foldl :: (b -> a -> b) -> b -> OrderedMap key a -> b # foldl' :: (b -> a -> b) -> b -> OrderedMap key a -> b # foldr1 :: (a -> a -> a) -> OrderedMap key a -> a # foldl1 :: (a -> a -> a) -> OrderedMap key a -> a # toList :: OrderedMap key a -> [a] # null :: OrderedMap key a -> Bool # length :: OrderedMap key a -> Int # elem :: Eq a => a -> OrderedMap key a -> Bool # maximum :: Ord a => OrderedMap key a -> a # minimum :: Ord a => OrderedMap key a -> a # sum :: Num a => OrderedMap key a -> a # product :: Num a => OrderedMap key a -> a #
Traversable (OrderedMap key) Source #
Methods traverse :: Applicative f => (a -> f b) -> OrderedMap key a -> f (OrderedMap key b) # sequenceA :: Applicative f => OrderedMap key (f a) -> f (OrderedMap key a) # mapM :: Monad m => (a -> m b) -> OrderedMap key a -> m (OrderedMap key b) # sequence :: Monad m => OrderedMap key (m a) -> m (OrderedMap key a) #
(Eq value, Eq key) => Eq (OrderedMap key value) Source #
Methods (==) :: OrderedMap key value -> OrderedMap key value -> Bool # (/=) :: OrderedMap key value -> OrderedMap key value -> Bool #
(Ord value, Ord key) => Ord (OrderedMap key value) Source #
Methods compare :: OrderedMap key value -> OrderedMap key value -> Ordering # (<) :: OrderedMap key value -> OrderedMap key value -> Bool # (<=) :: OrderedMap key value -> OrderedMap key value -> Bool # (>) :: OrderedMap key value -> OrderedMap key value -> Bool # (>=) :: OrderedMap key value -> OrderedMap key value -> Bool # max :: OrderedMap key value -> OrderedMap key value -> OrderedMap key value # min :: OrderedMap key value -> OrderedMap key value -> OrderedMap key value #
(Show value, Show key) => Show (OrderedMap key value) Source #
Methods showsPrec :: Int -> OrderedMap key value -> ShowS # show :: OrderedMap key value -> String # showList :: [OrderedMap key value] -> ShowS #
(Arbitrary key, Arbitrary value, Ord key) => Arbitrary (OrderedMap key value) Source #
Methods arbitrary :: Gen (OrderedMap key value) # shrink :: OrderedMap key value -> [OrderedMap key value] #

Construction

empty :: forall key value. OrderedMap key value Source #

The empty OrderedMap. O(1)

singleton :: forall key value. key -> value -> OrderedMap key value Source #

Create an ordered map containing a single entry. O(1)

orderedMap :: forall key value. Ord key => [(key, value)] -> Maybe (OrderedMap key value) Source #

Construct an ordered map from a list.

O(n log n).

If the list contains duplicate keys, then return Nothing. Otherwise, return an OrderedMap, preserving the order.

Querying

lookup :: forall key value. Ord key => key -> OrderedMap key value -> Maybe value Source #

Find a value in an ordered map.

O(log n)

Filtering

catMaybes :: Ord key => OrderedMap key (Maybe value) -> OrderedMap key value Source #

Take an ordered map with Maybe values and return the same map with all the Nothing values removed.

Combine

Union

unions :: forall key value. Ord key => [OrderedMap key value] -> Maybe (OrderedMap key value) Source #

The union of a list of ordered maps.

If any map shares a key with any other map, return Nothing.

Otherwise, return a new map containing all of the keys from all of the maps. The keys from the first map will appear first, followed by the second, and so forth.

O(m * n log (m * n)) where m is the number of maps, and n is the size of the largest map.

unionWith :: Ord key => (value -> value -> value) -> OrderedMap key value -> OrderedMap key value -> OrderedMap key value Source #

Append the second ordered map to the first, combining any shared elements with the given function.

unionsWith :: Ord key => (value -> value -> value) -> [OrderedMap key value] -> OrderedMap key value Source #

Append together a list of ordered maps, preserving ordering of keys. Combine any shared elements with the given function.

unionWithM :: (Monad m, Ord key) => (value -> value -> m value) -> OrderedMap key value -> OrderedMap key value -> m (OrderedMap key value) Source #

Take two ordered maps, append the second one to the first. If the second contains any keys that also appear in the first, combine the two values with the given function.

unionsWithM :: (Monad m, Ord key) => (value -> value -> m value) -> [OrderedMap key value] -> m (OrderedMap key value) Source #

Take a list of ordered maps and append them together. Any shared elements are combined using the given function.

Conversion

toList :: forall key value. Ord key => OrderedMap key value -> [(key, value)] Source #

Convert an ordered map to a list of keys and values. The list is guaranteed to be the same order as the order of insertion into the map.

O(n log n)

toMap :: OrderedMap key value -> Map key value Source #

Convert an ordered map to a regular map, losing insertion order.

keys :: OrderedMap key value -> [key] Source #

Get the list of keys from an ordered map, in order of appearance.

This list is guaranteed to have no duplicates.

values :: forall key value. Ord key => OrderedMap key value -> [value] Source #

Get the values from an ordered map, in order of appearance. O(n log n)

Properties

genOrderedMap :: forall key value. Ord key => Gen key -> Gen value -> Gen (OrderedMap key value) Source #

Generate an ordered map with the given key & value generators.