Implements "patience diff" and the patience algorithm for the longest increasing subsequence problem.
The difference between two lists, according to the "patience diff" algorithm.
An element of a computed difference.
Value taken from the "old" list, i.e. left argument to
Value taken from the "new" list, i.e. right argument to
|Both t t|
Value taken from both lists. Both values are provided, in case your type has a non-structural definition of equality.
Longest increasing subsequence
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.