Moduledhall-1.42.3Haskell2010

Dhall.Map

Map type used to represent records and unions

1 type
38 values

Packagedhall-1.42.3
Exports39
LanguageHaskell2010
LicenceBSD-3-Clause
SourceMap.hs

Type

1 declaration

datadata Map k v

A Map that remembers the original ordering of keys

This is primarily used so that formatting preserves field order

This is done primarily to avoid a dependency on insert-ordered-containers and also to improve performance

Instances18FoldableWithIndex, FunctorWithIndex, TraversableWithIndex, Lift, Functor, Foldable, …

Ord k => FoldableWithIndex k (Map k)Defined in dhall-1.42.3 · Dhall.Map
FunctorWithIndex k (Map k)Defined in dhall-1.42.3 · Dhall.Map
Ord k => TraversableWithIndex k (Map k)Defined in dhall-1.42.3 · Dhall.Map
(Lift k, Lift v) => Lift (Map k v)Defined in dhall-1.42.3 · Dhall.Map
Functor (Map k)Defined in dhall-1.42.3 · Dhall.Map
Ord k => Foldable (Map k)Defined in dhall-1.42.3 · Dhall.Map
Ord k => Traversable (Map k)Defined in dhall-1.42.3 · Dhall.Map
Ord k => IsList (Map k v)Defined in dhall-1.42.3 · Dhall.Map
(Ord k, Eq v) => Eq (Map k v)Defined in dhall-1.42.3 · Dhall.Map
(Data k, Data v, Ord k) => Data (Map k v)Defined in dhall-1.42.3 · Dhall.Map
(Ord k, Ord v) => Ord (Map k v)Defined in dhall-1.42.3 · Dhall.Map
Example1 expression
```
>>> fromList [("A",1),("B",2)] < fromList [("B",1),("A",0)]True
```
(Show k, Show v, Ord k) => Show (Map k v)Defined in dhall-1.42.3 · Dhall.Map
Generic (Map k v)Defined in dhall-1.42.3 · Dhall.Map
Ord k => Semigroup (Map k v)Defined in dhall-1.42.3 · Dhall.Map
Property
```
prop> \x y z -> x <> (y <> z) == (x <> y) <> (z :: Map Int Int)
```

Ord k => Monoid (Map k v)Defined in dhall-1.42.3 · Dhall.Map

Property

prop> \x -> x <> mempty == (x :: Map Int Int)

Property

prop> \x -> mempty <> x == (x :: Map Int Int)

(NFData k, NFData v) => NFData (Map k v)Defined in dhall-1.42.3 · Dhall.Map
type Rep (Map k v) = D1 ('MetaData "Map" "Dhall.Map" "dhall-1.42.3-5OoAJpk2vIpARwiStLO8GU" 'False) (C1 ('MetaCons "Map" 'PrefixI 'False) (S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map k v)) :*: S1 ('MetaSel 'Nothing 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Keys k))))Defined in dhall-1.42.3 · Dhall.Map
type Item (Map k v) = (k, v)Defined in dhall-1.42.3 · Dhall.Map

Construction

5 declarations

valueempty :: Ord k => Map k v

Create an empty Map

valuesingleton :: k -> v -> Map k v

Create a Map from a single key-value pair

Example1 expression

>>> singleton "A" 1fromList [("A",1)]

valuefromList :: Ord k => [(k, v)] -> Map k v

Create a Map from a list of key-value pairs

Example2 expressions

>>> fromList [("B",1),("A",2)]  -- The map preserves orderfromList [("B",1),("A",2)]>>> fromList [("A",1),("A",2)]  -- For duplicates, later values take precedencefromList [("A",2)]

Note that this handling of duplicates means that fromList is not a monoid homomorphism:

Example2 expressions

>>> fromList [(1, True)] <> fromList [(1, False)]fromList [(1,True)]>>> fromList ([(1, True)] <> [(1, False)])fromList [(1,False)]

valuefromListWithKey :: Ord k => (k -> v -> v -> v) -> [(k, v)] -> Map k v

Create a Map from a list of key-value pairs with a combining function.

Example1 expression

>>> fromListWithKey (\k v1 v2 -> k ++ v1 ++ v2) [("B","v1"),("A","v2"),("B","v3")]fromList [("B","Bv3v1"),("A","v2")]

valuefromMap :: Map k v -> Map k v

Create a Map from a Data.Map.Strict.Map

Constructing unordered Maps

2 declarations

valueunorderedSingleton :: k -> v -> Map k v

Create a Map from a single key-value pair.

Any further operations on this map will not retain the order of the keys.

Example1 expression

>>> unorderedSingleton "A" 1fromList [("A",1)]

valueunorderedFromList :: Ord k => [(k, v)] -> Map k v

Create a Map from a list of key-value pairs

Any further operations on this map will not retain the order of the keys.

Example3 expressions

>>> unorderedFromList []fromList []>>> unorderedFromList [("B",1),("A",2)]  -- The map /doesn't/ preserve orderfromList [("A",2),("B",1)]>>> unorderedFromList [("A",1),("A",2)]  -- For duplicates, later values take precedencefromList [("A",2)]

Sorting

2 declarations

valuesort :: Map k v -> Map k v

Sort the keys of a Map, forgetting the original ordering

sort (sort x) = sort x

Example1 expression

>>> sort (fromList [("B",1),("A",2)])fromList [("A",2),("B",1)]

valueisSorted :: Eq k => Map k v -> Bool

Check if the keys of a Map are already sorted

isSorted (sort m) = True

Example2 expressions

>>> isSorted (fromList [("B",1),("A",2)])  -- Sortedness is based only on keysFalse>>> isSorted (fromList [("A",2),("B",1)])True

Insertion

2 declarations

valueinsert :: Ord k => k -> v -> Map k v -> Map k v

Insert a key-value pair into a Map, overriding any previous value stored underneath the same key, if present

insert = insertWith (\v _ -> v)

Example2 expressions

>>> insert "C" 1 (fromList [("B",2),("A",3)])  -- Values are inserted on leftfromList [("C",1),("B",2),("A",3)]>>> insert "C" 1 (fromList [("C",2),("A",3)])  -- New value takes precedencefromList [("C",1),("A",3)]

valueinsertWith :: Ord k => (v -> v -> v) -> k -> v -> Map k v -> Map k v

Insert a key-value pair into a Map, using the supplied function to combine the new value with any old value underneath the same key, if present

Example2 expressions

>>> insertWith (+) "C" 1 (fromList [("B",2),("A",3)])  -- No collisionfromList [("C",1),("B",2),("A",3)]>>> insertWith (+) "C" 1 (fromList [("C",2),("A",3)])  -- CollisionfromList [("C",3),("A",3)]

Deletion/Update

6 declarations

valuedelete :: Ord k => k -> Map k v -> Map k v

Delete a key from a Map if present, otherwise return the original Map

Example2 expressions

>>> delete "B" (fromList [("C",1),("B",2),("A",3)])fromList [("C",1),("A",3)]>>> delete "D" (fromList [("C",1),("B",2),("A",3)])fromList [("C",1),("B",2),("A",3)]

valuefilter :: Ord k => (a -> Bool) -> Map k a -> Map k a

Keep all values that satisfy the given predicate

Example2 expressions

>>> filter even (fromList [("C",3),("B",2),("A",1)])fromList [("B",2)]>>> filter odd (fromList [("C",3),("B",2),("A",1)])fromList [("C",3),("A",1)]

valuepartition :: Ord k => (a -> Bool) -> Map k a -> (Map k a, Map k a)

Split the map into values that do and don't satisfy the predicate

Example2 expressions

>>> partition even (fromList [("C",3),("B",2),("A",1)])(fromList [("B",2)],fromList [("C",3),("A",1)])>>> partition odd (fromList [("C",3),("B",2),("A",1)])(fromList [("C",3),("A",1)],fromList [("B",2)])

valuerestrictKeys :: Ord k => Map k a -> Set k -> Map k a

Restrict a Map to only those keys found in a Data.Set.Set.

Example1 expression

>>> restrictKeys (fromList [("A",1),("B",2)]) (Data.Set.fromList ["A"])fromList [("A",1)]

valuewithoutKeys :: Ord k => Map k a -> Set k -> Map k a

Remove all keys in a Data.Set.Set from a Map

Example1 expression

>>> withoutKeys (fromList [("A",1),("B",2)]) (Data.Set.fromList ["A"])fromList [("B",2)]

valuemapMaybe :: Ord k => (a -> Maybe b) -> Map k a -> Map k b

Transform all values in a Map using the supplied function, deleting the key if the function returns Nothing

Example1 expression

>>> mapMaybe Data.Maybe.listToMaybe (fromList [("C",[1]),("B",[]),("A",[3])])fromList [("C",1),("A",3)]

Query

4 declarations

valuelookup :: Ord k => k -> Map k v -> Maybe v

Retrieve a key from a Map

lookup k mempty = empty

lookup k (x <> y) = lookup k y <|> lookup k x

Example2 expressions

>>> lookup "A" (fromList [("B",1),("A",2)])Just 2>>> lookup "C" (fromList [("B",1),("A",2)])Nothing

valuemember :: Ord k => k -> Map k v -> Bool

Check if a key belongs to a Map

member k mempty = False

member k (x <> y) = member k x || member k y

Example2 expressions

>>> member "A" (fromList [("B",1),("A",2)])True>>> member "C" (fromList [("B",1),("A",2)])False

valueuncons :: Ord k => Map k v -> Maybe (k, v, Map k v)

Retrieve the first key, value of the Map, if present, and also returning the rest of the Map.

uncons mempty = empty

uncons (singleton k v) = (k, v, mempty)

Example2 expressions

>>> uncons (fromList [("C",1),("B",2),("A",3)])Just ("C",1,fromList [("B",2),("A",3)])>>> uncons (fromList [])Nothing

valuesize :: Map k v -> Int

Example1 expression

>>> size (fromList [("A",1)])1

Combine

6 declarations

valueunion :: Ord k => Map k v -> Map k v -> Map k v

Combine two Maps, preferring keys from the first Map

union = unionWith (\v _ -> v)

Example2 expressions

>>> union (fromList [("D",1),("C",2)]) (fromList [("B",3),("A",4)])fromList [("D",1),("C",2),("B",3),("A",4)]>>> union (fromList [("D",1),("C",2)]) (fromList [("C",3),("A",4)])fromList [("D",1),("C",2),("A",4)]

valueunionWith :: Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v

Combine two Maps using a combining function for colliding keys

Example2 expressions

>>> unionWith (+) (fromList [("D",1),("C",2)]) (fromList [("B",3),("A",4)])fromList [("D",1),("C",2),("B",3),("A",4)]>>> unionWith (+) (fromList [("D",1),("C",2)]) (fromList [("C",3),("A",4)])fromList [("D",1),("C",5),("A",4)]

valueouterJoin

:: Ord k
=> a -> c
-> b -> c
-> k -> a -> b -> c
-> Map k a
-> Map k b
-> Map k c

A generalised unionWith.

Example1 expression

>>> outerJoin Left Left (\k a b -> Right (k, a, b)) (fromList [("A",1),("B",2)]) (singleton "A" 3)fromList [("A",Right ("A",1,3)),("B",Left 2)]

This function is much inspired by the Data.Semialign.Semialign class.

valueintersection :: Ord k => Map k a -> Map k b -> Map k a

Combine two Map on their shared keys, keeping the value from the first Map

intersection = intersectionWith (\v _ -> v)

Example1 expression

>>> intersection (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])fromList [("B",2)]

valueintersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c

Combine two Maps on their shared keys, using the supplied function to combine values from the first and second Map

Example1 expression

>>> intersectionWith (+) (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])fromList [("B",5)]

valuedifference :: Ord k => Map k a -> Map k b -> Map k a

Compute the difference of two Maps by subtracting all keys from the second Map from the first Map

Example1 expression

>>> difference (fromList [("C",1),("B",2)]) (fromList [("B",3),("A",4)])fromList [("C",1)]

Traversals

5 declarations

valuemapWithKey :: (k -> a -> b) -> Map k a -> Map k b

Transform the values of a Map using their corresponding key

mapWithKey (pure id) = id

mapWithKey (liftA2 (.) f g) = mapWithKey f . mapWithKey g

mapWithKey f mempty = mempty

mapWithKey f (x <> y) = mapWithKey f x <> mapWithKey f y

Example1 expression

>>> mapWithKey (,) (fromList [("B",1),("A",2)])fromList [("B",("B",1)),("A",("A",2))]

valuetraverseWithKey

:: (Ord k, Applicative f)
=> k -> a -> f b
-> Map k a
-> f (Map k b)

Traverse all of the key-value pairs in a Map, in their original order

Example1 expression

>>> traverseWithKey (,) (fromList [("B",1),("A",2)])("BA",fromList [("B",1),("A",2)])

valueunorderedTraverseWithKey

:: (Ord k, Applicative f)
=> k -> a -> f b
-> Map k a
-> f (Map k b)

Same as traverseWithKey, except that the order of effects is not necessarily the same as the order of the keys

valueunorderedTraverseWithKey_

:: (Ord k, Applicative f)
=> k -> a -> f ()
-> Map k a
-> f ()

Traverse all of the key-value pairs in a Map, not preserving their original order, where the result of the computation can be forgotten.

Note that this is a strict traversal, fully traversing the map even when the Applicative is lazy in the remaining elements.

valuefoldMapWithKey :: (Monoid m, Ord k) => (k -> a -> m) -> Map k a -> m

Fold all of the key-value pairs in a Map, in their original order

Example1 expression

>>> foldMapWithKey (,) (fromList [("B",[1]),("A",[2])])("BA",[1,2])

Conversions

6 declarations

valuetoList :: Ord k => Map k v -> [(k, v)]

Convert a Map to a list of key-value pairs in the original order of keys

Example1 expression

>>> toList (fromList [("B",1),("A",2)])[("B",1),("A",2)]

valuetoAscList :: Map k v -> [(k, v)]

Convert a Map to a list of key-value pairs in ascending order of keys

valuetoMap :: Map k v -> Map k v

Convert a Dhall.Map.Map to a Data.Map.Strict.Map

Example1 expression

>>> toMap (fromList [("B",1),("A",2)]) -- Order is lost upon conversionfromList [("A",2),("B",1)]

valuekeys :: Map k v -> [k]

Return the keys from a Map in their original order

Example1 expression

>>> keys (fromList [("B",1),("A",2)])["B","A"]

valuekeysSet :: Map k v -> Set k

Return the Data.Set.Set of the keys

Example1 expression

>>> keysSet (fromList [("B",1),("A",2)])fromList ["A","B"]

valueelems :: Ord k => Map k v -> [v]

Return the values from a Map in their original order.

Example1 expression

>>> elems (fromList [("B",1),("A",2)])[1,2]