Copyright | (c) wren romano 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 :: SimpleWhenMissing a c -> SimpleWhenMissing b c -> SimpleWhenMatched a b c -> IntMap a -> IntMap b -> IntMap c
- zipWithMaybeMatched :: Applicative f => (Key -> x -> y -> Maybe z) -> WhenMatched f x y z
- zipWithMatched :: Applicative f => (Key -> x -> y -> z) -> WhenMatched f x y z
- mapMaybeMissing :: Applicative f => (Key -> x -> Maybe y) -> WhenMissing f x y
- dropMissing :: Applicative f => WhenMissing f x y
- preserveMissing :: Applicative f => WhenMissing f x x
- mapMissing :: Applicative f => (Key -> x -> y) -> WhenMissing f x y
- filterMissing :: Applicative f => (Key -> x -> Bool) -> WhenMissing f x x
- data WhenMissing f x y
- data WhenMatched f x y z
- mergeA :: Applicative f => WhenMissing f a c -> WhenMissing f b c -> WhenMatched f a b c -> IntMap a -> IntMap b -> f (IntMap c)
- zipWithMaybeAMatched :: (Key -> x -> y -> f (Maybe z)) -> WhenMatched f x y z
- zipWithAMatched :: Applicative f => (Key -> x -> y -> f z) -> WhenMatched f x y z
- traverseMaybeMissing :: Applicative f => (Key -> x -> f (Maybe y)) -> WhenMissing f x y
- traverseMissing :: Applicative f => (Key -> x -> f y) -> WhenMissing f x y
- filterAMissing :: Applicative f => (Key -> x -> f Bool) -> WhenMissing f x x
- mapWhenMissing :: (Applicative f, Monad f) => (a -> b) -> WhenMissing f x a -> WhenMissing f x b
- mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b
- runWhenMatched :: WhenMatched f x y z -> Key -> x -> y -> f (Maybe z)
- runWhenMissing :: WhenMissing f x y -> Key -> x -> f (Maybe y)

## Simple merge tactic types

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 x z`

is an abstract
representation of a function of type `Key -> x -> Maybe z`

.

type SimpleWhenMatched = WhenMatched Identity Source #

A tactic for dealing with keys present in both maps in `merge`

.

A tactic of type `SimpleWhenMatched x y z`

is an abstract
representation of a function of type `Key -> x -> y -> Maybe z`

.

## General combining function

:: SimpleWhenMissing a c | What to do with keys in |

-> SimpleWhenMissing b c | What to do with keys in |

-> SimpleWhenMatched a b c | What to do with keys in both |

-> IntMap a | Map |

-> IntMap b | Map |

-> IntMap 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 => (Key -> x -> y -> Maybe z) -> WhenMatched f 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 :: (Key -> x -> y -> Maybe z) -> SimpleWhenMatched x y z

zipWithMatched :: Applicative f => (Key -> x -> y -> z) -> WhenMatched f 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 :: (Key -> x -> y -> z) -> SimpleWhenMatched x y z

`WhenMissing`

tactics

mapMaybeMissing :: Applicative f => (Key -> x -> Maybe y) -> WhenMissing f 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 :: (Key -> x -> Maybe y) -> SimpleWhenMissing x y

mapMaybeMissing f = traverseMaybeMissing (\k x -> pure (f k x))

but `mapMaybeMissing`

uses fewer unnecessary `Applicative`

operations.

dropMissing :: Applicative f => WhenMissing f x y Source #

Drop all the entries whose keys are missing from the other map.

dropMissing :: SimpleWhenMissing x y

dropMissing = mapMaybeMissing (\_ _ -> Nothing)

but `dropMissing`

is much faster.

preserveMissing :: Applicative f => WhenMissing f x x Source #

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

preserveMissing :: SimpleWhenMissing x x

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

but `preserveMissing`

is much faster.

mapMissing :: Applicative f => (Key -> x -> y) -> WhenMissing f x y Source #

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

mapMissing :: (k -> x -> y) -> SimpleWhenMissing x y

mapMissing f = mapMaybeMissing (\k x -> Just $ f k x)

but `mapMissing`

is somewhat faster.

filterMissing :: Applicative f => (Key -> x -> Bool) -> WhenMissing f x x Source #

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

filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing 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 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 `Key -> x -> f (Maybe z)`

.

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

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

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

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

data WhenMatched f x y z Source #

A tactic for dealing with keys present in both maps in `merge`

or `mergeA`

.

A tactic of type `WhenMatched f x y z`

is an abstract representation
of a function of type `Key -> x -> y -> f (Maybe z)`

.

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

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

Functor f => Functor (WhenMatched f x y) Source # | |

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

## Applicative general combining function

:: Applicative f | |

=> WhenMissing f a c | What to do with keys in |

-> WhenMissing f b c | What to do with keys in |

-> WhenMatched f a b c | What to do with keys in both |

-> IntMap a | Map |

-> IntMap b | Map |

-> f (IntMap 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 :: (Key -> x -> y -> f (Maybe z)) -> WhenMatched f 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 => (Key -> x -> y -> f z) -> WhenMatched f 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`

tactics

traverseMaybeMissing :: Applicative f => (Key -> x -> f (Maybe y)) -> WhenMissing f 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 => (Key -> x -> f y) -> WhenMissing f x y Source #

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

filterAMissing :: Applicative f => (Key -> x -> f Bool) -> WhenMissing f x x Source #

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 :: (Applicative f, Monad f) => (a -> b) -> WhenMissing f x a -> WhenMissing f x b Source #

Map covariantly over a

.`WhenMissing`

f x

mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b Source #

Map covariantly over a

.`WhenMatched`

f x y

## Miscellaneous functions on tactics

runWhenMatched :: WhenMatched f x y z -> Key -> x -> y -> f (Maybe z) Source #

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

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

.

runWhenMissing :: WhenMissing f x y -> Key -> x -> f (Maybe y) Source #

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

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

.