Copyright | (c) David Feuer 2016 |
---|---|

License | BSD-style |

Maintainer | libraries@haskell.org |

Stability | provisional |

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.Lazy.Merge then they will not.

## Efficiency note

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.

- type SimpleWhenMissing = WhenMissing Identity
- type SimpleWhenMatched = WhenMatched Identity
- merge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c
- zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z
- zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z
- mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y
- dropMissing :: Applicative f => WhenMissing f k x y
- preserveMissing :: Applicative f => WhenMissing f k x x
- mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y
- filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x
- data WhenMissing f k x y
- data WhenMatched f k x y z
- mergeA :: (Applicative f, Ord k) => WhenMissing f k a c -> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b -> f (Map k c)
- zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z
- zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z
- traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y
- traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y
- filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x
- mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b
- mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f k x y a -> WhenMatched f k x y b
- runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z)
- runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y)

## Simple merge tactic types

type SimpleWhenMissing = WhenMissing Identity

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 `

.

type SimpleWhenMatched = WhenMatched Identity

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 `

.

## General combining function

:: 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 0.5.8

`WhenMatched`

tactics

zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z

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

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`

tactics

mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y

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

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.

preserveMissing :: Applicative f => WhenMissing f k x x

Preserve, unchanged, the entries whose keys are missing from the other map.

preserveMissing :: SimpleWhenMissing k x x

preserveMissing = Lazy.Merge.mapMaybeMissing (\_ x -> Just x)

but `preserveMissing`

is much faster.

mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y

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

Filter the entries whose keys are missing from the other map.

filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x

filterMissing f = Lazy.Merge.mapMaybeMissing $ \k x -> guard (f k x) *> Just x

but this should be a little faster.

## Applicative merge tactic types

data WhenMissing f k x y

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) `

.

(Applicative f, Monad f) => Category * (WhenMissing f k) | |

(Applicative f, Monad f) => Monad (WhenMissing f k x) | Equivalent to |

(Applicative f, Monad f) => Functor (WhenMissing f k x) | |

(Applicative f, Monad f) => Applicative (WhenMissing f k x) | Equivalent to |

data WhenMatched f k x y z

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) `

.

(Monad f, Applicative f) => Category * (WhenMatched f k x) | |

(Monad f, Applicative f) => Monad (WhenMatched f k x y) | Equivalent to |

Functor f => Functor (WhenMatched f k x y) | |

(Monad f, Applicative f) => Applicative (WhenMatched f k x y) | Equivalent to |

## Applicative general combining function

:: (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 0.5.8

`WhenMatched`

tactics

zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z

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

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`

tactics

traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y

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

Traverse over the entries whose keys are missing from the other map.

filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x

Filter the entries whose keys are missing from the other map
using some `Applicative`

action.

filterAMissing f = Lazy.Merge.traverseMaybeMissing $ k x -> (b -> guard b *> Just x) $ f k x

but this should be a little faster.

## Covariant maps for tactics

mapWhenMissing :: Functor f => (a -> b) -> WhenMissing f k x a -> WhenMissing f k x b

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

Map covariantly over a

.`WhenMatched`

f k x y

## Miscellaneous functions on tactics

runWhenMatched :: WhenMatched f k x y z -> k -> x -> y -> f (Maybe z)

Along with zipWithMaybeAMatched, witnesses the isomorphism between
`WhenMatched f k x y z`

and `k -> x -> y -> f (Maybe z)`

.

runWhenMissing :: WhenMissing f k x y -> k -> x -> f (Maybe y)

Along with traverseMaybeMissing, witnesses the isomorphism between
`WhenMissing f k x y`

and `k -> x -> f (Maybe y)`

.