HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Modulepatience-0.3Haskell2010

Patience

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

  • 1 type
  • 2 values
  • Packagepatience-0.3
  • Exports3
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourcePatience.hs

Patience diff

2 declarations
valuediff :: Ord a => [a] -> [a] -> [Item a]
#

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

datadata Item a
#

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.

Instances6Functor, Eq, Data, Ord, Read, Show
  • Functor ItemDefined in patience-0.3 · Patience
  • Eq a => Eq (Item a)Defined in patience-0.3 · Patience
  • Data a => Data (Item a)Defined in patience-0.3 · Patience
  • Ord a => Ord (Item a)Defined in patience-0.3 · Patience
  • Read a => Read (Item a)Defined in patience-0.3 · Patience
  • Show a => Show (Item a)Defined in patience-0.3 · Patience

Longest increasing subsequence

1 declaration
valuelongestIncreasing :: [(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.