patience-0.3: Patience diff and longest increasing subsequence

Safe Haskell | Safe-Inferred
Language | Haskell2010

Patience

Contents

- Patience diff
- Longest increasing subsequence

Description

Implements "patience diff" and the patience algorithm for the longest increasing subsequence problem.

Synopsis

- diff :: Ord a => [a] -> [a] -> [Item a]
- data Item a
  - = Old a
  - | New a
  - | Both a a
- longestIncreasing :: [(Int, a)] -> [(Int, a)]

# Patience diff

diff :: Ord a => [a] -> [a] -> [Item a] Source #

The difference between two lists, according to the "patience diff" algorithm.

data Item a Source #

An element of a computed difference.

Constructors

Old a | Value taken from the "old" list, i.e. left argument to `diff`
New a | Value taken from the "new" list, i.e. right argument to `diff`
Both a a | Value taken from both lists. Both values are provided, in case your type has a non-structural definition of equality.

#### Instances

Instances details

Functor Item Source # |
Instance details Defined in Patience Methods fmap :: (a -> b) -> Item a -> Item b Source # (<$) :: a -> Item b -> Item a Source #
Data a => Data (Item a) Source # |

Instance details

Defined in Patience

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Item a -> c (Item a) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Item a) Source #

toConstr :: Item a -> Constr Source #

dataTypeOf :: Item a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Item a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Item a)) Source #

gmapT :: (forall b. Data b => b -> b) -> Item a -> Item a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Item a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Item a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> Item a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Item a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Item a -> m (Item a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Item a -> m (Item a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Item a -> m (Item a) Source #

Read a => Read (Item a) Source # |
Instance details Defined in Patience Methods readsPrec :: Int -> ReadS (Item a) Source # readList :: ReadS [Item a] Source # readPrec :: ReadPrec (Item a) Source # readListPrec :: ReadPrec [Item a] Source #
Show a => Show (Item a) Source # |
Instance details Defined in Patience Methods showsPrec :: Int -> Item a -> ShowS Source # show :: Item a -> String Source # showList :: [Item a] -> ShowS Source #
Eq a => Eq (Item a) Source # |
Instance details Defined in Patience Methods (==) :: Item a -> Item a -> Bool Source # (/=) :: Item a -> Item a -> Bool Source #
Ord a => Ord (Item a) Source # |
Instance details Defined in Patience Methods compare :: Item a -> Item a -> Ordering Source # (<) :: Item a -> Item a -> Bool Source # (<=) :: Item a -> Item a -> Bool Source # (>) :: Item a -> Item a -> Bool Source # (>=) :: Item a -> Item a -> Bool Source # max :: Item a -> Item a -> Item a Source # min :: Item a -> Item a -> Item a Source #

# Longest increasing subsequence

longestIncreasing :: [(Int, a)] -> [(Int, a)] Source #

Given: a list of distinct integers. Picks a subset of the integers in the same order, i.e. a subsequence, with the property that

- it is monotonically increasing, and
- it is at least as long as any other such subsequence.

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.