Backtracking with cut via a distributive law and left-zero monoids
Maciej Piróg, Sam Staton · Journal of Functional Programming · 2017
Abstract We employ the framework of algebraic effects to augment the list monad with the pruning cut operator known from Prolog. We give two descriptions of the resulting monad: as the monad of free left-zero monoids, and as a composition via a distributive law of the list monad and the ‘unary idempotent operation’ monad. The scope delimiter of cut arises as a handler.