Jamie Snape

Loopless Functional Algorithms

Abstract

Loopless algorithms generate successive combinatorial patterns in constant time, producing the first in time linear to the size of input. Although originally formulated in an imperative setting, this thesis proposes a functional interpretation of these algorithms in the lazy language Haskell. Since it may not be possible to produce a pattern in constant time, a list of integers generated using the library function unfoldr determines the transitions between consecutive patterns. The generation of Gray codes, permutations, ideals of posets and combinations illustrate applications of loopless algorithms in both imperative and functional form, particularly derivations of the Koda-Ruskey and Johnson-Trotter algorithms. Common themes in the construction of loopless imperative algorithms, such as focus pointers, doubly-linked lists and coroutines, contrast greatly with the functional uses of real-time queues, tree traversals, fusion and tupling.

Full Document

PDF (623 KB)

GitHub Repository

LooplessFunctionalAlgorithms (Haskell Source Code)

Citation

Jamie Snape, Loopless Functional Algorithms, Master's thesis, Computing Laboratory, University of Oxford, Oxford, UK, 2005, advised by Richard S. Bird