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.