W3cubDocs

/Haskell 8

Data.Map.Merge.Strict

Copyright (c) David Feuer 2016
License BSD-style
Maintainer [email protected]
Portability portable
Safe Haskell Safe
Language Haskell98

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.

preserveMissing inconsistency

For historical reasons, the preserved values are /not/ forced. To force them, use preserveMissing'.

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

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

General combining function

merge Source

Arguments

:: Ord k
=> SimpleWhenMissing k a c

What to do with keys in m1 but not m2

-> SimpleWhenMissing k b c

What to do with keys in m2 but not m1

-> SimpleWhenMatched k a b c

What to do with keys in both m1 and m2

-> Map k a

Map m1

-> Map k b

Map m2

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

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 preserveMissing dropMissing (zipWithMatched f)
symmetricDifference = merge preserveMissing preserveMissing (zipWithMaybeMatched $ \ _ _ _ -> Nothing)
mapEachPiece f g h = merge (mapMissing f) (mapMissing g) (zipWithMatched h)

Since: containers-0.5.9

WhenMatched tactics

zipWithMaybeMatched :: 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 tactics

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

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

Force the entries whose keys are missing from the other map and otherwise preserve them unchanged.

preserveMissing' :: SimpleWhenMissing k x x
preserveMissing' = Merge.Lazy.mapMaybeMissing (\_ x -> Just $! x)

but preserveMissing' is quite a bit 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

Applicative merge tactic types

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

Instances
Instances details
(Applicative f, Monad f) => Category (WhenMissing f k :: Type -> Type -> Type)

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

id :: forall (a :: k0). WhenMissing f k a a Source

(.) :: forall (b :: k0) (c :: k0) (a :: k0). 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 ReaderT k (ReaderT x (MaybeT f)) .

Since: containers-0.5.9

Instance details

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

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

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

fmap :: (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 ReaderT k (ReaderT x (MaybeT f)) .

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

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

Instances
Instances details
(Monad f, Applicative f) => Category (WhenMatched f k x :: Type -> Type -> Type)

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

id :: forall (a :: k0). WhenMatched f k x a a Source

(.) :: forall (b :: k0) (c :: k0) (a :: k0). 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 ReaderT k (ReaderT x (ReaderT y (MaybeT f)))

Since: containers-0.5.9

Instance details

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

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

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

fmap :: (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 ReaderT k (ReaderT x (ReaderT y (MaybeT f)))

Since: containers-0.5.9

Instance details

Defined in Data.Map.Internal

Methods

pure :: 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 general combining function

mergeA Source

Arguments

:: (Applicative f, Ord k)
=> WhenMissing f k a c

What to do with keys in m1 but not m2

-> WhenMissing f k b c

What to do with keys in m2 but not m1

-> WhenMatched f k a b c

What to do with keys in both m1 and m2

-> Map k a

Map m1

-> Map k b

Map m2

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

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

The 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

Covariant maps for tactics

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.

Miscellaneous functions on tactics

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.8.3/docs/html/libraries/containers-0.6.2.1/Data-Map-Merge-Strict.html