Copyright | (c) David Feuer 2016 |
---|---|
License | BSD-style |
Maintainer | [email protected] |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell98 |
This module defines an API for writing functions that merge two maps. The key functions are merge
and mergeA
. Each of these can be used with several different "merge tactics".
The merge
and mergeA
functions are shared by the lazy and strict modules. Only the choice of merge tactics determines strictness. If you use mapMissing
from this module then the results will be forced before they are inserted. If you use mapMissing
from Data.Map.Merge.Lazy then they will not.
The Category
, Applicative
, and Monad
instances for WhenMissing
tactics are included because they are valid. However, they are inefficient in many cases and should usually be avoided. The instances for WhenMatched
tactics should not pose any major efficiency problems.
Since: containers-0.5.9
type SimpleWhenMissing = WhenMissing Identity Source
A tactic for dealing with keys present in one map but not the other in merge
.
A tactic of type SimpleWhenMissing k x z
is an abstract representation of a function of type k -> x -> Maybe z
.
Since: containers-0.5.9
type SimpleWhenMatched = WhenMatched Identity Source
A tactic for dealing with keys present in both maps in merge
.
A tactic of type SimpleWhenMatched k x y z
is an abstract representation of a function of type k -> x -> y -> Maybe z
.
Since: containers-0.5.9
:: Ord k | |
=> SimpleWhenMissing k a c | What to do with keys in |
-> SimpleWhenMissing k b c | What to do with keys in |
-> SimpleWhenMatched k a b c | What to do with keys in both |
-> Map k a | Map |
-> Map k b | Map |
-> Map k c |
Merge two maps.
merge
takes two WhenMissing
tactics, a WhenMatched
tactic and two maps. It uses the tactics to merge the maps. Its behavior is best understood via its fundamental tactics, mapMaybeMissing
and zipWithMaybeMatched
.
Consider
merge (mapMaybeMissing g1) (mapMaybeMissing g2) (zipWithMaybeMatched f) m1 m2
Take, for example,
m1 = [(0, a), (1, b), (3,c), (4, d)] m2 = [(1, "one"), (2, "two"), (4, "three")]
merge
will first 'align'
these maps by key:
m1 = [(0, a), (1, b), (3,c), (4, d)] m2 = [(1, "one"), (2, "two"), (4, "three")]
It will then pass the individual entries and pairs of entries to g1
, g2
, or f
as appropriate:
maybes = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
This produces a Maybe
for each key:
keys = 0 1 2 3 4 results = [Nothing, Just True, Just False, Nothing, Just True]
Finally, the Just
results are collected into a map:
return value = [(1, True), (2, False), (4, True)]
The other tactics below are optimizations or simplifications of mapMaybeMissing
for special cases. Most importantly,
dropMissing
drops all the keys.preserveMissing
leaves all the entries alone.When merge
is given three arguments, it is inlined at the call site. To prevent excessive inlining, you should typically use merge
to define your custom combining functions.
Examples:
unionWithKey f = merge preserveMissing preserveMissing (zipWithMatched f)
intersectionWithKey f = merge dropMissing dropMissing (zipWithMatched f)
differenceWith f = merge diffPreserve diffDrop f
symmetricDifference = merge diffPreserve diffPreserve (\ _ _ _ -> Nothing)
mapEachPiece f g h = merge (diffMapWithKey f) (diffMapWithKey g)
Since: containers-0.5.9
WhenMatched
tacticszipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z Source
When a key is found in both maps, apply a function to the key and values and maybe use the result in the merged map.
zipWithMaybeMatched :: (k -> x -> y -> Maybe z) -> SimpleWhenMatched k x y z
zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z Source
When a key is found in both maps, apply a function to the key and values and use the result in the merged map.
zipWithMatched :: (k -> x -> y -> z) -> SimpleWhenMatched k x y z
WhenMissing
tacticsmapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y Source
Map over the entries whose keys are missing from the other map, optionally removing some. This is the most powerful SimpleWhenMissing
tactic, but others are usually more efficient.
mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))
but mapMaybeMissing
uses fewer unnecessary Applicative
operations.
dropMissing :: Applicative f => WhenMissing f k x y Source
Drop all the entries whose keys are missing from the other map.
dropMissing :: SimpleWhenMissing k x y
dropMissing = mapMaybeMissing (\_ _ -> Nothing)
but dropMissing
is much faster.
Since: containers-0.5.9
preserveMissing :: Applicative f => WhenMissing f k x x Source
Preserve, unchanged, the entries whose keys are missing from the other map.
preserveMissing :: SimpleWhenMissing k x x
preserveMissing = Merge.Lazy.mapMaybeMissing (\_ x -> Just x)
but preserveMissing
is much faster.
Since: containers-0.5.9
mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y Source
Map over the entries whose keys are missing from the other map.
mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
mapMissing f = mapMaybeMissing (\k x -> Just $ f k x)
but mapMissing
is somewhat faster.
filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x Source
Filter the entries whose keys are missing from the other map.
filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x
filterMissing f = Merge.Lazy.mapMaybeMissing $ \k x -> guard (f k x) *> Just x
but this should be a little faster.
Since: containers-0.5.9
data WhenMissing f k x y Source
A tactic for dealing with keys present in one map but not the other in merge
or mergeA
.
A tactic of type WhenMissing f k x z
is an abstract representation of a function of type k -> x -> f (Maybe z)
.
Since: containers-0.5.9
(Applicative f, Monad f) => Category (WhenMissing f k :: Type -> Type -> Type) | Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodsid :: WhenMissing f k a a Source (.) :: WhenMissing f k b c -> WhenMissing f k a b -> WhenMissing f k a c Source | |
(Applicative f, Monad f) => Monad (WhenMissing f k x) |
Equivalent to Since: containers-0.5.9 |
Defined in Data.Map.Internal Methods(>>=) :: WhenMissing f k x a -> (a -> WhenMissing f k x b) -> WhenMissing f k x b Source (>>) :: WhenMissing f k x a -> WhenMissing f k x b -> WhenMissing f k x b Source return :: a -> WhenMissing f k x a Source fail :: String -> WhenMissing f k x a Source | |
(Applicative f, Monad f) => Functor (WhenMissing f k x) | Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodsfmap :: (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b Source (<$) :: a -> WhenMissing f k x b -> WhenMissing f k x a Source | |
(Applicative f, Monad f) => Applicative (WhenMissing f k x) |
Equivalent to Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodspure :: a -> WhenMissing f k x a Source (<*>) :: WhenMissing f k x (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b Source liftA2 :: (a -> b -> c) -> WhenMissing f k x a -> WhenMissing f k x b -> WhenMissing f k x c Source (*>) :: WhenMissing f k x a -> WhenMissing f k x b -> WhenMissing f k x b Source (<*) :: WhenMissing f k x a -> WhenMissing f k x b -> WhenMissing f k x a Source |
data WhenMatched f k x y z Source
A tactic for dealing with keys present in both maps in merge
or mergeA
.
A tactic of type WhenMatched f k x y z
is an abstract representation of a function of type k -> x -> y -> f (Maybe z)
.
Since: containers-0.5.9
(Monad f, Applicative f) => Category (WhenMatched f k x :: Type -> Type -> Type) | Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodsid :: WhenMatched f k x a a Source (.) :: WhenMatched f k x b c -> WhenMatched f k x a b -> WhenMatched f k x a c Source | |
(Monad f, Applicative f) => Monad (WhenMatched f k x y) |
Equivalent to Since: containers-0.5.9 |
Defined in Data.Map.Internal Methods(>>=) :: WhenMatched f k x y a -> (a -> WhenMatched f k x y b) -> WhenMatched f k x y b Source (>>) :: WhenMatched f k x y a -> WhenMatched f k x y b -> WhenMatched f k x y b Source return :: a -> WhenMatched f k x y a Source fail :: String -> WhenMatched f k x y a Source | |
Functor f => Functor (WhenMatched f k x y) | Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodsfmap :: (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b Source (<$) :: a -> WhenMatched f k x y b -> WhenMatched f k x y a Source | |
(Monad f, Applicative f) => Applicative (WhenMatched f k x y) |
Equivalent to Since: containers-0.5.9 |
Defined in Data.Map.Internal Methodspure :: a -> WhenMatched f k x y a Source (<*>) :: WhenMatched f k x y (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b Source liftA2 :: (a -> b -> c) -> WhenMatched f k x y a -> WhenMatched f k x y b -> WhenMatched f k x y c Source (*>) :: WhenMatched f k x y a -> WhenMatched f k x y b -> WhenMatched f k x y b Source (<*) :: WhenMatched f k x y a -> WhenMatched f k x y b -> WhenMatched f k x y a Source |
:: (Applicative f, Ord k) | |
=> WhenMissing f k a c | What to do with keys in |
-> WhenMissing f k b c | What to do with keys in |
-> WhenMatched f k a b c | What to do with keys in both |
-> Map k a | Map |
-> Map k b | Map |
-> f (Map k c) |
An applicative version of merge
.
mergeA
takes two WhenMissing
tactics, a WhenMatched
tactic and two maps. It uses the tactics to merge the maps. Its behavior is best understood via its fundamental tactics, traverseMaybeMissing
and zipWithMaybeAMatched
.
Consider
mergeA (traverseMaybeMissing g1) (traverseMaybeMissing g2) (zipWithMaybeAMatched f) m1 m2
Take, for example,
m1 = [(0, a), (1, b), (3,c), (4, d)] m2 = [(1, "one"), (2, "two"), (4, "three")]
mergeA
will first 'align'
these maps by key:
m1 = [(0, a), (1, b), (3,c), (4, d)] m2 = [(1, "one"), (2, "two"), (4, "three")]
It will then pass the individual entries and pairs of entries to g1
, g2
, or f
as appropriate:
actions = [g1 0 a, f 1 b "one", g2 2 "two", g1 3 c, f 4 d "three"]
Next, it will perform the actions in the actions
list in order from left to right.
keys = 0 1 2 3 4 results = [Nothing, Just True, Just False, Nothing, Just True]
Finally, the Just
results are collected into a map:
return value = [(1, True), (2, False), (4, True)]
The other tactics below are optimizations or simplifications of traverseMaybeMissing
for special cases. Most importantly,
dropMissing
drops all the keys.preserveMissing
leaves all the entries alone.mapMaybeMissing
does not use the Applicative
context.When mergeA
is given three arguments, it is inlined at the call site. To prevent excessive inlining, you should generally only use mergeA
to define custom combining functions.
Since: containers-0.5.9
WhenMatched
tacticsThe tactics described for merge
work for mergeA
as well. Furthermore, the following are available.
zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z Source
When a key is found in both maps, apply a function to the key and values, perform the resulting action, and maybe use the result in the merged map.
This is the fundamental WhenMatched
tactic.
zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z Source
When a key is found in both maps, apply a function to the key and values to produce an action and use its result in the merged map.
WhenMissing
tacticsThe tactics described for merge
work for mergeA
as well. Furthermore, the following are available.
traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y Source
Traverse over the entries whose keys are missing from the other map, optionally producing values to put in the result. This is the most powerful WhenMissing
tactic, but others are usually more efficient.
traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y Source
Traverse over the entries whose keys are missing from the other map.
filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x Source
Filter the entries whose keys are missing from the other map using some Applicative
action.
filterAMissing f = Merge.Lazy.traverseMaybeMissing $ k x -> (b -> guard b *> Just x) $ f k x
but this should be a little faster.
Since: containers-0.5.9
mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b Source
Map covariantly over a WhenMissing f k x
.
mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b Source
Map covariantly over a WhenMatched f k x y
.
runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z) Source
Along with zipWithMaybeAMatched, witnesses the isomorphism between WhenMatched f k x y z
and k -> x -> y -> f (Maybe z)
.
Since: containers-0.5.9
runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y) Source
Along with traverseMaybeMissing, witnesses the isomorphism between WhenMissing f k x y
and k -> x -> f (Maybe y)
.
Since: containers-0.5.9
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/8.6.1/docs/html/libraries/containers-0.6.0.1/Data-Map-Merge-Strict.html