EUVIMEDEUVIMED entdecken
Crossref

The Tortoise and the Hare Algorithm for Finite Lists, Compositionally

Olivier Danvy

ACM Transactions on Programming Languages and Systems · 31.03.2023 · 45 (1) · 1-35

DOI: 10.1145/3564619 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Programming Languages and Systems, online erschienen am 03.03.2023. Verfasst von Olivier Danvy. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 44 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the tortoise-and-hare algorithm, when the fast pointer reaches the end of a finite list, the slow pointer points to the middle of this list. In the early 2000’s, this property was found to make it possible to program a palindrome detector for immutable lists that operates in one recursive traversal of the given list and performs the smallest possible number of comparisons, using the “There And Back Again” (TABA) recursion pattern. In this article, this palindrome detector is reconstructed in OCaml, formalized with the Coq Proof Assistant, and proved to be correct. More broadly, this article presents a compositional account of the tortoise-and-hare algorithm for finite lists. Concretely, compositionality means that programs that use a fast and a slow pointer can be expressed with an ordinary fold function for lists and reasoned about using ordinary structural induction on the given list. This article also contains a dozen new applications of the TABA recursion pattern and of its tail-recursive variant, “There and Forth Again”.

Zitieren

APA

Danvy, O. (2023). The Tortoise and the Hare Algorithm for Finite Lists, Compositionally. ACM Transactions on Programming Languages and Systems, 45(1), 1-35. https://doi.org/10.1145/3564619

Vancouver

Danvy O. The Tortoise and the Hare Algorithm for Finite Lists, Compositionally. ACM Transactions on Programming Languages and Systems. 2023;45(1):1-35. doi:10.1145/3564619

BibTeX
@article{Danvy2023,
  author = {Danvy, Olivier},
  title = {The Tortoise and the Hare Algorithm for Finite Lists, Compositionally},
  journal = {ACM Transactions on Programming Languages and Systems},
  year = {2023},
  volume = {45},
  number = {1},
  pages = {1--35},
  doi = {10.1145/3564619}
}
Kostenlos starten →