Freer Monads, More Extensible Effects
📜 Abstract
We present a rational reconstruction of extensible effects, the recently proposed alternative to monad transformers, as the confluence of efforts to make effectful computations compose. Free monads and then extensible effects emerge from the straightforward term representation of an effectful computation, as more and more boilerplate is abstracted away. The generalization process further leads to freer monads, constructed without the Functor constraint. The continuation exposed in freer monads can then be represented as an efficient type-aligned data structure. The end result is the algorithmically efficient extensible effects library, which is not only more comprehensible but also faster than earlier implementations. As an illustration of the new library, we show three surprisingly simple applications: non-determinism with committed choice (LogicT), catching IO exceptions in the presence of other effects, and the semi-automatic management of file handles and other resources through monadic regions. We extensively use and promote the new sort of ‘laziness’, which underlies the left Kan extension: instead of performing an operation, keep its operands and pretend it is done.
✨ Summary
Summary
The paper develops extensible effects by progressively abstracting a direct algebraic representation of effectful computations. It first derives free monads from request signatures, then introduces freer monads, which store each operation’s continuation explicitly and therefore do not require the operation signature to be a Functor. This construction is presented as an instance of the left Kan extension: instead of immediately performing a structural operation such as mapping, the representation records its operands and defers the operation.
Extensibility is obtained by combining freer monads with an open union of effect signatures. Type-level effect membership permits effectful client code to remain polymorphic over additional effects, while modular interpreters can handle or encapsulate individual effects. The paper emphasizes that effect interpretation order, rather than a fixed transformer-stack order, determines effect interaction.
The initial freer-monad representation has quadratic behavior for left-associated binds. The paper addresses this by representing continuations as heterogeneous, type-aligned queues (FTCQueue). Appending continuation segments becomes constant-time on average, reducing the problematic example from quadratic to linear time. Benchmarks report strong performance for deep effect stacks and substantial improvements over the earlier extensible-effects implementation. However, the approach remains much slower than specialized State implementations in the single-effect benchmark, largely because GHC optimizes conventional state-transformer code particularly well.
Three applications demonstrate the expressiveness of the framework: non-determinism with committed choice, interception of IO exceptions while preserving other effect state, and statically scoped resource management through monadic regions. The paper’s central technical result is that a freer-monad representation, an open-union effect system, modular handlers, and type-aligned continuation queues can provide a comparatively general and efficient alternative to monad transformers.
Influence
The paper directly influenced Haskell libraries such as freer-simple, whose documentation identifies it as an implementation based on this work. (hdiff.luite.com) Its freer-monad and open-union design also became part of the broader implementation lineage of extensible-effect libraries; contemporary documentation for the Scala eff library explicitly describes itself as based on these ideas. (atnos-org.github.io) Later educational and language-library work continues to cite the paper and use its freer construction as a reference point, including Lean libraries implementing free monads without a Functor requirement. (freely.endofunctor.dev) The available evidence supports a concrete influence on subsequent effect-system libraries and teaching materials, but does not establish broad industrial adoption.