-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Patience diff and longest increasing subsequence -- -- This library implements the "patience diff" algorithm, as well as the -- patience algorithm for the longest increasing subsequence problem. -- -- Patience diff computes the difference between two lists, for example -- the lines of two versions of a source file. It provides a good balance -- of performance, nice output for humans, and implementation simplicity. -- For more information, see -- http://alfedenzo.livejournal.com/170301.html and -- http://bramcohen.livejournal.com/73318.html. @package patience @version 0.3 -- | Implements "patience diff" and the patience algorithm for the longest -- increasing subsequence problem. module Patience -- | The difference between two lists, according to the "patience diff" -- algorithm. diff :: Ord a => [a] -> [a] -> [Item a] -- | An element of a computed difference. data Item a -- | Value taken from the "old" list, i.e. left argument to diff Old :: a -> Item a -- | Value taken from the "new" list, i.e. right argument to diff New :: a -> Item a -- | Value taken from both lists. Both values are provided, in case your -- type has a non-structural definition of equality. Both :: a -> a -> Item a -- | Given: a list of distinct integers. Picks a subset of the integers in -- the same order, i.e. a subsequence, with the property that -- -- -- -- This function uses patience sort: -- http://en.wikipedia.org/wiki/Patience_sorting. For -- implementation reasons, the actual list returned is the reverse of the -- subsequence. -- -- You can pair each integer with an arbitrary annotation, which will be -- carried through the algorithm. longestIncreasing :: [(Int, a)] -> [(Int, a)] instance GHC.Base.Functor Patience.Item instance Data.Data.Data a => Data.Data.Data (Patience.Item a) instance GHC.Read.Read a => GHC.Read.Read (Patience.Item a) instance GHC.Show.Show a => GHC.Show.Show (Patience.Item a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Patience.Item a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Patience.Item a) instance GHC.Show.Show a => GHC.Show.Show (Patience.Piece a) -- | This module provides a lossless way to do diffing between two -- Maps, and ways to manipulate the diffs. module Patience.Map -- | The result of a diff of an entry within two Maps. -- -- In two Maps 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). data Delta a Delta :: !a -> !a -> Delta a Same :: !a -> Delta a Old :: !a -> Delta a New :: !a -> Delta a -- | Takes two Maps and returns a Map from the same key type -- to Delta a, where Delta a encodes -- differences between entries. diff :: (Eq a, Ord k) => Map k a -> Map k a -> Map k (Delta a) -- | Potentially get the Same value out of a Delta. getSame :: Eq a => Delta a -> Maybe a -- | Potentially get the Old value out of a Delta. getOld :: Delta a -> Maybe a -- | Potentially get the New value out of a Delta. getNew :: Delta a -> Maybe a -- | Potentially get the Changed value out of a Delta. getDelta :: Delta a -> Maybe (a, a) -- | Get the original values out of the Delta. getOriginals :: Delta a -> (Maybe a, Maybe a) -- | Is the Delta an encoding of same values? isSame :: Eq a => Delta a -> Bool -- | Is the Delta an encoding of old values? isOld :: Delta a -> Bool -- | Is the Delta an encoding of new values? isNew :: Delta a -> Bool -- | Is the Delta an encoding of changed values? isDelta :: Delta a -> Bool -- | Retrieve the Same values out of the diff map. toSame :: Eq a => Map k (Delta a) -> Map k a -- | Retrieve only the Old values out of the diff map. toOld :: Map k (Delta a) -> Map k a -- | Retrieve only the New values out of the diff map. toNew :: Map k (Delta a) -> Map k a -- | Retrieve only the DeltaUnit values out of the diff map. toDelta :: Map k (Delta a) -> Map k (a, a) -- | Reconstruct both original Maps. toOriginals :: Map k (Delta a) -> (Map k a, Map k a) -- | 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. mapSame :: Eq a => (a -> b) -> Map k (Delta a) -> Map k b -- | 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. mapOld :: (a -> b) -> Map k (Delta a) -> Map k b -- | 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. mapNew :: (a -> b) -> Map k (Delta a) -> Map k b -- | Map over all the Same values, preserving the remaining values -- in the map. mapSame' :: Eq a => (a -> a) -> Map k (Delta a) -> Map k (Delta a) -- | Map over all the Old values, preserving the remaining values in -- the map. mapOld' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a) -- | Map over all the New values, preserving the remaining values in -- the map. mapNew' :: (a -> a) -> Map k (Delta a) -> Map k (Delta a) instance Data.Traversable.Traversable Patience.Map.Delta instance GHC.Show.Show a => GHC.Show.Show (Patience.Map.Delta a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Patience.Map.Delta a) instance GHC.Generics.Generic1 Patience.Map.Delta instance GHC.Generics.Generic (Patience.Map.Delta a) instance GHC.Base.Functor Patience.Map.Delta instance Data.Foldable.Foldable Patience.Map.Delta instance GHC.Classes.Eq a => GHC.Classes.Eq (Patience.Map.Delta a)