Constraint Programming (CP) is a declarative paradigm where a programmer models a problem in terms of constraints over some set of variables. Monadic Constraint Programming (MCP) integrates CP with functional programming by modeling the constraint solver as a monad threaded through a monadic search tree. This abstraction allows us to define search as a first-class object which can be constructed from composable search transformers.

We introduce \emph{Effectful Constraint Programming} (ECP), a re-imagining of monadic constraint programming using the increasingly-popular framework of algebraic effects and handlers. To overcome the performance drawbacks of effects, we use multi-stage programming to generate efficient search procedures from high-level, abstract descriptions.