The bits between the lambdas: Binary data in a lazy functional language

For the programmer, storage media are usually assumed to have a minimum ato mic unit of transfer of one byte. However, sometimes it is useful to have a n even finer storage granularity of one bit, for instance in order to compr ess data. This paper describes an API in the lazy functional language Haskell for tre ating storage media as arbitrary-length streams of bits, without byte-align ment constraints. So far as possible, storage media are treated uniformly. In particular, bit-stream memory and binary files share the same API - a ne w and useful abstraction over memory management and file management. This u niformity of access leads to a novel technique for lazy random-access to fi les in a purely functional manner. We also describe a technique for automat ically deriving compressed binary representations of user-defined data stru ctures, whose operations provide both in-heap data compression and convenie nt high-level binary I/O. Of many possible applications, we illustrate the processing of Huffman-enco ded image data, and a bibliographic information system which uses lazy B-tr ees for efficient storage management.