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.