The Tortoise and the Hare Algorithm for Finite Lists, Compositionally
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.
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}
}
EUVIMED