一句话：用 Huet zipper 设计纯函数式最长上升趋势算法，兼得渐近最优与实际高效。
最长递增子序列问题通常以命令式方式实现，依赖数组获得常数时间的查找与更新。若直接改用函数式序列，虽可保持相同的渐近运行时间，但实际性能显著变差。本文是一篇函数式珍珠，提出一种纯函数式解法：利用 Huet zipper 显式刻画搜索、查找与更新之间的交互，从而在保持渐近最优性的同时获得良好的实际效率。作者还改进了文献中常见命令式解法的自适应行为。其核心贡献是给出真正函数式、渐近最优且实践高效的最长上升趋势问题实现，说明 zipper 可有效桥接持久化数据结构与数组式原地更新的性能需求。
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.
@article{paperbot3053,
title = {Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)},
author = {Alexander Dinges and Ralf Hinze},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {ICFP},
year = {2025},
doi = {10.1145/3747520}
}