Tag Archives: Data Structure

Out-of-core functional programming with type-based primitives

T-R. Chuang and S-C. Mu,. In 2nd International Workshop on Practical Aspects of Declarative Languages, January 2000.
[GZipped Postscript]

We formulate and experiment with type-based primitives (such as fold and unfold operations) for out-of-core processing of functional data structures. We follow the view that recursive data types are fixed points of polynomial type constructors. This view leads to a clear separation of the semantics and the implementations of recursive data types. We provide monadic implementations of the type-based primitives so that the intermediate data structures used for the executions of the primitives can be placed in out-of-core storage. The parametric module facility of Objective Caml is further used to package the out-of-core implementations. The resulting out-of-core user code retains the same program structure of the in-core user code and can be as elegant.