Loopless Functional Algorithms

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