Concurrent monads for shared state

Abstract

In the monad-based approach to functional programming with effects, sequential composition, the primary high-level control structure for combining effectful functions, takes a special role. In this article, we advocate the idea that parallel composition should be recognized as a high-level control structure on an equal footing with sequential composition. We promote the concept of concurrent monad, which axiomatizes both sequential and parallel composition, and illustrate the approach by describing two concurrent monads for interleaving shared state concurrency: one of resumptions, the other of collections of traces.