Mutable Data Structures and Composable References in a Pure Functional Language,
Koji Kagawa


Abstract

We propose composable references as tools to handle mutable data structures in monadic-style functional programs. They enable us to express mutable data structures efficiently, for example, to avoid unnecessary indirections and to avoid copying. A composable reference is a reference which is parameterized over the type of the underlying mutable data structure used as the state and intuitively is a location of a field (or more generally, a substructure) relative to the parameterized state. Composable references can be composed as functions. Composable references make stateful programs concise by allowing mutable data structures to be passed implicitly.