Data.Algorithm.Patience

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

Patience diff

diff :: Ord t => [t] -> [t] -> [Item t]

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

data Item t

An element of a computed difference.

Constructors

Old t

Value taken from the "old" list, i.e. left argument to diff

New t

Value taken from the "new" list, i.e. right argument to diff

Both t t

Value taken from both lists. Both values are provided, in case your type has a non-structural definition of equality.

Instances

Functor Item

Typeable1 Item

Eq t => Eq (Item t)

Data t => Data (Item t)

Ord t => Ord (Item t)

Read t => Read (Item t)

Show t => Show (Item t)

itemChar :: Item t -> Char

The character '-' or '+' or ' ' for Old or New or Both respectively.

itemValue :: Item t -> t

The value from an Item. For Both, returns the "old" value.

Longest increasing subsequence

longestIncreasing :: [(Int, a)] -> [(Int, 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

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