Purely Functional Compressed Bit Vectors with Applications and Implementations

The study of compressed data structures strives to represent information on a computer concisely — using as little space as possible. Compressed bit vectors are the simplest compressed data structure. They are used as a basis for more complex data structures with applications in, for example, computational biology. Functional programming is a programming paradigm that represents computation using functions without side-effects (such as mutation). Data structures that are representable in and suitable for functional programming are termed functional data structures. Functional data structures are also persistent: operations on them do not destroy previous versions. This thesis provides implementations of functional compressed bit vectors in the purely functional programming language Haskell. The implemented structures are analyzed and benchmarked against established imperative (C++) implementations. Applications of compressed bit vectors are also surveyed. This includes compressed wavelet trees, an implementation of which is also presented