Copyright | (c) wren romano 2016 |
---|---|
License | BSD-style |
Maintainer | libraries@haskell.org |
Portability | portable |
Safe Haskell | Safe |
Language | Haskell2010 |
Data.IntMap.Merge.Lazy
Contents
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
Data.Map.Merge.Strict
then the results will be forced before
they are inserted. If you use
mapMissing
from
this module 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: 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
- lmapWhenMissing :: (b -> a) -> WhenMissing f a x -> WhenMissing f b x
- contramapFirstWhenMatched :: (b -> a) -> WhenMatched f a y z -> WhenMatched f b y z
- contramapSecondWhenMatched :: (b -> a) -> WhenMatched f x a z -> WhenMatched f x b z
- 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
.
Since: 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 x y z
is an abstract
representation of a function of type
Key -> x -> y -> Maybe z
.
Since: 0.5.9
General combining function
Arguments
:: 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.9
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
Since: 0.5.9
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
Since: 0.5.9
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.
Since: 0.5.9
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.
Since: 0.5.9
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 = Merge.Lazy.mapMaybeMissing (\_ x -> Just x)
but
preserveMissing
is much faster.
Since: 0.5.9
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.
Since: 0.5.9
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 = Merge.Lazy.mapMaybeMissing $ \k x -> guard (f k x) *> Just x
but this should be a little faster.
Since: 0.5.9
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)
.
Since: 0.5.9
Instances
( Applicative f, Monad f) => Category ( WhenMissing f :: Type -> Type -> Type ) Source # |
Since: 0.5.9 |
Defined in Data.IntMap.Internal Methods id :: forall (a :: k). WhenMissing f a a Source # (.) :: forall (b :: k) (c :: k) (a :: k). WhenMissing f b c -> WhenMissing f a b -> WhenMissing f a c Source # |
|
( Applicative f, Monad f) => Monad ( WhenMissing f x) Source # |
Equivalent to
Since: 0.5.9 |
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 # |
|
( Applicative f, Monad f) => Functor ( WhenMissing f x) Source # |
Since: 0.5.9 |
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) Source # |
Equivalent to
Since: 0.5.9 |
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 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)
.
Since: 0.5.9
Instances
( Monad f, Applicative f) => Category ( WhenMatched f x :: Type -> Type -> Type ) Source # |
Since: 0.5.9 |
Defined in Data.IntMap.Internal Methods id :: forall (a :: k). WhenMatched f x a a Source # (.) :: forall (b :: k) (c :: k) (a :: k). 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) Source # |
Equivalent to
Since: 0.5.9 |
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 # |
|
Functor f => Functor ( WhenMatched f x y) Source # |
Since: 0.5.9 |
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) Source # |
Equivalent to
Since: 0.5.9 |
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
Arguments
:: 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 theApplicative
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.9
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.
Since: 0.5.9
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.
Since: 0.5.9
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.
Since: 0.5.9
traverseMissing :: Applicative f => ( Key -> x -> f y) -> WhenMissing f x y Source #
Traverse over the entries whose keys are missing from the other map.
Since: 0.5.9
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 = Merge.Lazy.traverseMaybeMissing $ \k x -> (\b -> guard b *> Just x) <$> f k x
but this should be a little faster.
Since: 0.5.9
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
Since: 0.5.9
mapWhenMatched :: Functor f => (a -> b) -> WhenMatched f x y a -> WhenMatched f x y b Source #
Map covariantly over a
.
WhenMatched
f x y
Since: 0.5.9
Contravariant maps for tactics
lmapWhenMissing :: (b -> a) -> WhenMissing f a x -> WhenMissing f b x Source #
Map contravariantly over a
.
WhenMissing
f _ x
Since: 0.5.9
contramapFirstWhenMatched :: (b -> a) -> WhenMatched f a y z -> WhenMatched f b y z Source #
Map contravariantly over a
.
WhenMatched
f _ y z
Since: 0.5.9
contramapSecondWhenMatched :: (b -> a) -> WhenMatched f x a z -> WhenMatched f x b z Source #
Map contravariantly over a
.
WhenMatched
f x _ z
Since: 0.5.9
Miscellaneous tactic functions
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)
.
Since: 0.5.9
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)
.
Since: 0.5.9