Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)

Reference. Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)

Alexander Dinges, Ralf Hinze · ICFP · 2025 · program-calculation · PDF · DOI · pldb

Solutions to the longest increasing subsequence problem are typically implemented imperatively, relying on arrays for constant-time lookups and updates. Replacing these arrays with functional sequences allows a purely functional solution with the same asymptotic running time, but with significantly worse practical performance. In this pearl, we present a purely functional approach that is not only asymptotically optimal, but also efficient in practice. The core idea is to exploit the interplay between search, lookup, and update operations through Huet’s zipper. In addition, we improve the adaptive behaviour of imperative solutions commonly found in the literature.

Cite

Cite as @dinges-2025-truly (helia, typst) · \cite{dinges-2025-truly} (LaTeX)

BibTeX

bibtex · 1 line

@article{dinges-2025-truly, title={Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)}, volume={9}, ISSN={2475-1421}, url={http://dx.doi.org/10.1145/3747520}, DOI={10.1145/3747520}, number={ICFP}, journal={Proceedings of the ACM on Programming Languages}, publisher={Association for Computing Machinery (ACM)}, author={Dinges, Alexander and Hinze, Ralf}, year={2025}, month=Aug, pages={463–478} }

hayagriva YAML (typst)

yaml · 18 lines

dinges-2025-truly:
  type: article
  title: Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
  author:
  - Dinges, Alexander
  - Hinze, Ralf
  date: 2025-08
  page-range: 463-478
  url: http://dx.doi.org/10.1145/3747520
  serial-number:
    doi: 10.1145/3747520
    issn: 2475-1421
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    publisher: Association for Computing Machinery (ACM)
    issue: ICFP
    volume: 9

Download: dinges-2025-truly.bib · dinges-2025-truly.yml

Cites 9 works (2 here)

With notes (2)

Binary search—think positive dinges-2025-binaryJFP · 2025

DOI · pldb

Algorithm Design with Haskell bird-2020-algorithm2020

DOI

External (7)

Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl) Artifact (2025)
The Derivative of a Regular Type is its Type of One-Hole Contexts (2001)
Red-black trees in a functional setting (1999)
Constructing Red-Black Trees (1999)
The Zipper (1997)
A Method of Programming (1988)
The Science of Programming (1981)