patience-0.3: Patience diff and longest increasing subsequence

Safe Haskell | Safe-Inferred
Language | Haskell2010

Patience.Map

Contents

- Types
- Diffing
- Case analysis on `Delta`
- Construction of special maps from a diff
- Mapping

Description

This module provides a lossless way to do diffing between two `Map`s, and ways to manipulate the diffs.

Synopsis

- data Delta a
  - = Delta !a !a
  - | Same !a
  - | Old !a
  - | New !a
- diff :: (Eq a, Ord k) => Map k a -> Map k a -> Map k (Delta a)
- getSame :: Eq a => Delta a -> Maybe a
- getOld :: Delta a -> Maybe a
- getNew :: Delta a -> Maybe a
- getDelta :: Delta a -> Maybe (a, a)
- getOriginals :: Delta a -> (Maybe a, Maybe a)
- isSame :: Eq a => Delta a -> Bool
- isOld :: Delta a -> Bool
- isNew :: Delta a -> Bool
- isDelta :: Delta a -> Bool
- toSame :: Eq a => Map k (Delta a) -> Map k a
- toOld :: Map k (Delta a) -> Map k a
- toNew :: Map k (Delta a) -> Map k a
- toDelta :: Map k (Delta a) -> Map k (a, a)
- toOriginals :: Map k (Delta a) -> (Map k a, Map k a)
- mapSame :: Eq a => (a -> b) -> Map k (Delta a) -> Map k b
- mapOld :: (a -> b) -> Map k (Delta a) -> Map k b
- mapNew :: (a -> b) -> Map k (Delta a) -> Map k b
- mapSame' :: Eq a => (a -> a) -> Map k (Delta a) -> Map k (Delta a)
- mapOld' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a)
- mapNew' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a)

# Types

data Delta a Source #

The result of a diff of an entry within two `Map`s.

In two `Map`s m1 and m2, when performing a diff, this type encodes the following situations:

Same key, different values: Stores the two values in the Delta constructor.

Same key, same values: Stores the value in the Same constructor.

Key exists in m1 but not m2: Stores the value in the Old constructor.

Key exists in m2 but not m1: Stores the value in the New constructor.

This behaviour ensures that we don't lose any information, meaning we can reconstruct either of the original `Map` `k` `a` from a `Map` `k` (`Delta` `a`). (Note that this slightly differs from `diff`, which does not care about the possibility of reconstruction).

Constructors

Delta !a !a |
Same !a |
Old !a |
New !a |

#### Instances

Instances details

Functor Delta Source # |
Instance details Defined in Patience.Map Methods fmap :: (a -> b) -> Delta a -> Delta b Source # (<$) :: a -> Delta b -> Delta a Source #
Foldable Delta Source # |

Instance details

Defined in Patience.Map

Methods

fold :: Monoid m => Delta m -> m Source #

foldMap :: Monoid m => (a -> m) -> Delta a -> m Source #

foldMap' :: Monoid m => (a -> m) -> Delta a -> m Source #

foldr :: (a -> b -> b) -> b -> Delta a -> b Source #

foldr' :: (a -> b -> b) -> b -> Delta a -> b Source #

foldl :: (b -> a -> b) -> b -> Delta a -> b Source #

foldl' :: (b -> a -> b) -> b -> Delta a -> b Source #

foldr1 :: (a -> a -> a) -> Delta a -> a Source #

foldl1 :: (a -> a -> a) -> Delta a -> a Source #

toList :: Delta a -> [a] Source #

null :: Delta a -> Bool Source #

length :: Delta a -> Int Source #

elem :: Eq a => a -> Delta a -> Bool Source #

maximum :: Ord a => Delta a -> a Source #

minimum :: Ord a => Delta a -> a Source #

sum :: Num a => Delta a -> a Source #

product :: Num a => Delta a -> a Source #

Traversable Delta Source # |
Instance details Defined in Patience.Map Methods traverse :: Applicative f => (a -> f b) -> Delta a -> f (Delta b) Source # sequenceA :: Applicative f => Delta (f a) -> f (Delta a) Source # mapM :: Monad m => (a -> m b) -> Delta a -> m (Delta b) Source # sequence :: Monad m => Delta (m a) -> m (Delta a) Source #
Generic1 Delta Source # |

Instance details

Defined in Patience.Map

Associated Types

type Rep1 Delta |

Instance details

Defined in Patience.Map

type Rep1 Delta = D1 ('MetaData "Delta" "Patience.Map" "patience-0.3-BUQSUKlc433Kg6bMD0heYH" 'False) ((C1 ('MetaCons "Delta" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1) :+: C1 ('MetaCons "Same" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1)) :+: (C1 ('MetaCons "Old" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1) :+: C1 ('MetaCons "New" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1)))

Methods

from1 :: Delta a -> Rep1 Delta a Source #

to1 :: Rep1 Delta a -> Delta a Source #

Generic (Delta a) Source # |

Instance details

Defined in Patience.Map

Associated Types

type Rep (Delta a) |

Instance details

Defined in Patience.Map

type Rep (Delta a) = D1 ('MetaData "Delta" "Patience.Map" "patience-0.3-BUQSUKlc433Kg6bMD0heYH" 'False) ((C1 ('MetaCons "Delta" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a)) :+: C1 ('MetaCons "Same" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a))) :+: (C1 ('MetaCons "Old" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a)) :+: C1 ('MetaCons "New" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a))))

Methods

from :: Delta a -> Rep (Delta a) x Source #

to :: Rep (Delta a) x -> Delta a Source #

Show a => Show (Delta a) Source # |
Instance details Defined in Patience.Map Methods showsPrec :: Int -> Delta a -> ShowS Source # show :: Delta a -> String Source # showList :: [Delta a] -> ShowS Source #
Eq a => Eq (Delta a) Source # |
Instance details Defined in Patience.Map Methods (==) :: Delta a -> Delta a -> Bool Source # (/=) :: Delta a -> Delta a -> Bool Source #
Ord a => Ord (Delta a) Source # |
Instance details Defined in Patience.Map Methods compare :: Delta a -> Delta a -> Ordering Source # (<) :: Delta a -> Delta a -> Bool Source # (<=) :: Delta a -> Delta a -> Bool Source # (>) :: Delta a -> Delta a -> Bool Source # (>=) :: Delta a -> Delta a -> Bool Source # max :: Delta a -> Delta a -> Delta a Source # min :: Delta a -> Delta a -> Delta a Source #
type Rep1 Delta Source # |

Instance details

Defined in Patience.Map

type Rep1 Delta = D1 ('MetaData "Delta" "Patience.Map" "patience-0.3-BUQSUKlc433Kg6bMD0heYH" 'False) ((C1 ('MetaCons "Delta" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1 :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1) :+: C1 ('MetaCons "Same" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1)) :+: (C1 ('MetaCons "Old" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1) :+: C1 ('MetaCons "New" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) Par1)))

type Rep (Delta a) Source # |

Instance details

Defined in Patience.Map

type Rep (Delta a) = D1 ('MetaData "Delta" "Patience.Map" "patience-0.3-BUQSUKlc433Kg6bMD0heYH" 'False) ((C1 ('MetaCons "Delta" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a)) :+: C1 ('MetaCons "Same" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a))) :+: (C1 ('MetaCons "Old" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a)) :+: C1 ('MetaCons "New" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 a))))

# Diffing

diff Source #

Arguments

:: (Eq a, Ord k) |
=> Map k a | first, old `Map`
-> Map k a | second, new `Map`
-> Map k (Delta a) | `Map` encoding the diff

Takes two `Map`s and returns a `Map` from the same key type to `Delta` `a`, where `Delta` `a` encodes differences between entries.

# Case analysis on `Delta`

getSame :: Eq a => Delta a -> Maybe a Source #

Potentially get the `Same` value out of a `Delta`.

getOld :: Delta a -> Maybe a Source #

Potentially get the `Old` value out of a `Delta`.

getNew :: Delta a -> Maybe a Source #

Potentially get the `New` value out of a `Delta`.

getDelta :: Delta a -> Maybe (a, a) Source #

Potentially get the `Changed` value out of a `Delta`.

getOriginals :: Delta a -> (Maybe a, Maybe a) Source #

Get the original values out of the `Delta`.

isSame :: Eq a => Delta a -> Bool Source #

Is the `Delta` an encoding of same values?

isOld :: Delta a -> Bool Source #

Is the `Delta` an encoding of old values?

isNew :: Delta a -> Bool Source #

Is the `Delta` an encoding of new values?

isDelta :: Delta a -> Bool Source #

Is the `Delta` an encoding of changed values?

# Construction of special maps from a diff

toSame :: Eq a => Map k (Delta a) -> Map k a Source #

Retrieve the `Same` values out of the diff map.

toOld :: Map k (Delta a) -> Map k a Source #

Retrieve only the `Old` values out of the diff map.

toNew :: Map k (Delta a) -> Map k a Source #

Retrieve only the `New` values out of the diff map.

toDelta :: Map k (Delta a) -> Map k (a, a) Source #

Retrieve only the `DeltaUnit` values out of the diff map.

toOriginals :: Map k (Delta a) -> (Map k a, Map k a) Source #

Reconstruct both original `Map`s.

# Mapping

mapSame :: Eq a => (a -> b) -> Map k (Delta a) -> Map k b Source #

Map over all `Same` values, returning a map of just the transformed values. This can be more efficient than calling `toSame` and then Data.Map's `map`.

mapOld :: (a -> b) -> Map k (Delta a) -> Map k b Source #

Map over all `Old` values, returning a map of just the transformed values. This can be more efficient than calling `toOld` and then Data.Map's `map`.

mapNew :: (a -> b) -> Map k (Delta a) -> Map k b Source #

Map over all `New` values, returning a map of just the transformed values. This can be more efficient than calling `toNew` and then Data.Map's `map`.

mapSame' :: Eq a => (a -> a) -> Map k (Delta a) -> Map k (Delta a) Source #

Map over all the `Same` values, preserving the remaining values in the map.

mapOld' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a) Source #

Map over all the `Old` values, preserving the remaining values in the map.

mapNew' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a) Source #

Map over all the `New` values, preserving the remaining values in the map.