Data.IntMap.Merge.Strict

containers-0.5.11.0: Assorted concrete container types

Copyright | (c) wren romano 2016
License | BSD-style
Maintainer | libraries@haskell.org
Portability | portable
Safe Haskell | Safe
Language | Haskell98

Data.IntMap.Merge.Strict

Contents

- Simple merge tactic types
- General combining function
  - `WhenMatched` tactics
  - `WhenMissing` tactics
- Applicative merge tactic types
- Applicative general combining function
  - `WhenMatched` tactics
  - `WhenMissing` tactics
- Covariant maps for tactics
- Miscellaneous functions on tactics

Description

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.

## 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.

Since: containers-0.5.9

Synopsis

- 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 #

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

Since: containers-0.5.9

type SimpleWhenMatched = WhenMatched Identity #

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

Since: containers-0.5.9

## General combining function

merge #

Arguments

:: SimpleWhenMissing a c | What to do with keys in `m1` but not `m2`
-> SimpleWhenMissing b c | What to do with keys in `m2` but not `m1`
-> SimpleWhenMatched a b c | What to do with keys in both `m1` and `m2`
-> IntMap a | Map `m1`
-> IntMap b | Map `m2`
-> 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: containers-0.5.9

### `WhenMatched` tactics

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

Since: containers-0.5.9

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

Since: containers-0.5.9

### `WhenMissing` tactics

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

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

but `mapMaybeMissing` uses fewer unnecessary `Applicative` operations.

Since: containers-0.5.9

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

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

    dropMissing :: SimpleWhenMissing x y

    dropMissing = mapMaybeMissing (\_ _ -> Nothing)

but `dropMissing` is much faster.

Since: containers-0.5.9

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

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

    preserveMissing :: SimpleWhenMissing x x

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

but `preserveMissing` is much faster.

Since: containers-0.5.9

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

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.

Since: containers-0.5.9

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

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

    filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing 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

## Applicative merge tactic types

data WhenMissing f 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 `Key -> x -> f (Maybe z)`.

Since: containers-0.5.9

Instances

(Applicative f, Monad f) => Category (WhenMissing f :: * -> * -> *) # | Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods id :: WhenMissing f a a Source # (.) :: WhenMissing f b c -> WhenMissing f a b -> WhenMissing f a c Source #
(Applicative f, Monad f) => Monad (WhenMissing f x) # | Equivalent to `ReaderT k (ReaderT x (MaybeT f))`. Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods (>>=) :: WhenMissing f x a -> (a -> WhenMissing f x b) -> WhenMissing f x b Source # (>>) :: WhenMissing f x a -> WhenMissing f x b -> WhenMissing f x b Source # return :: a -> WhenMissing f x a Source # fail :: String -> WhenMissing f x a Source #
(Applicative f, Monad f) => Functor (WhenMissing f x) # | Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods fmap :: (a -> b) -> WhenMissing f x a -> WhenMissing f x b Source # (<$) :: a -> WhenMissing f x b -> WhenMissing f x a Source #
(Applicative f, Monad f) => Applicative (WhenMissing f x) # | Equivalent to `ReaderT k (ReaderT x (MaybeT f))`. Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods pure :: a -> WhenMissing f x a Source # (<*>) :: WhenMissing f x (a -> b) -> WhenMissing f x a -> WhenMissing f x b Source # liftA2 :: (a -> b -> c) -> WhenMissing f x a -> WhenMissing f x b -> WhenMissing f x c Source # (*>) :: WhenMissing f x a -> WhenMissing f x b -> WhenMissing f x b Source # (<*) :: WhenMissing f x a -> WhenMissing f x b -> WhenMissing f x a Source #

data WhenMatched f x y z #

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

Since: containers-0.5.9

Instances

(Monad f, Applicative f) => Category (WhenMatched f x :: * -> * -> *) # | Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods id :: WhenMatched f x a a Source # (.) :: WhenMatched f x b c -> WhenMatched f x a b -> WhenMatched f x a c Source #
(Monad f, Applicative f) => Monad (WhenMatched f x y) # | Equivalent to `ReaderT Key (ReaderT x (ReaderT y (MaybeT f)))` Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods (>>=) :: WhenMatched f x y a -> (a -> WhenMatched f x y b) -> WhenMatched f x y b Source # (>>) :: WhenMatched f x y a -> WhenMatched f x y b -> WhenMatched f x y b Source # return :: a -> WhenMatched f x y a Source # fail :: String -> WhenMatched f x y a Source #
Functor f => Functor (WhenMatched f x y) # | Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods fmap :: (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b Source # (<$) :: a -> WhenMatched f x y b -> WhenMatched f x y a Source #
(Monad f, Applicative f) => Applicative (WhenMatched f x y) # | Equivalent to `ReaderT Key (ReaderT x (ReaderT y (MaybeT f)))` Since: containers-0.5.9
Instance details Defined in Data.IntMap.Internal Methods pure :: a -> WhenMatched f x y a Source # (<*>) :: WhenMatched f x y (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b Source # liftA2 :: (a -> b -> c) -> WhenMatched f x y a -> WhenMatched f x y b -> WhenMatched f x y c Source # (*>) :: WhenMatched f x y a -> WhenMatched f x y b -> WhenMatched f x y b Source # (<*) :: WhenMatched f x y a -> WhenMatched f x y b -> WhenMatched f x y a Source #

## Applicative general combining function

mergeA #

Arguments

:: Applicative f |
=> WhenMissing f a c | What to do with keys in `m1` but not `m2`
-> WhenMissing f b c | What to do with keys in `m2` but not `m1`
-> WhenMatched f a b c | What to do with keys in both `m1` and `m2`
-> IntMap a | Map `m1`
-> IntMap b | Map `m2`
-> 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: containers-0.5.9

### `WhenMatched` tactics

The tactics described for `merge` work for `mergeA` as well. Furthermore, the following are available.

zipWithMaybeAMatched :: (Key -> x -> y -> f (Maybe z)) -> WhenMatched f 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.

Since: containers-0.5.9

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

Since: containers-0.5.9

### `WhenMissing` tactics

The tactics described for `merge` work for `mergeA` as well. Furthermore, the following are available.

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

Since: containers-0.5.9

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

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

Since: containers-0.5.9

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

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

## Covariant maps for tactics

mapWhenMissing :: (Applicative f, Monad f) => (a -> b) -> WhenMissing f x a -> WhenMissing f x b #

Map covariantly over a ``WhenMissing` f x`.

Since: containers-0.5.9

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

Map covariantly over a ``WhenMatched` f x y`.

Since: containers-0.5.9

## Miscellaneous functions on tactics

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

Along with zipWithMaybeAMatched, witnesses the isomorphism between `WhenMatched f x y z` and `Key -> x -> y -> f (Maybe z)`.

Since: containers-0.5.9

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

Along with traverseMaybeMissing, witnesses the isomorphism between `WhenMissing f x y` and `Key -> x -> f (Maybe y)`.

Since: containers-0.5.9