[Haskell-cafe] Two-continuation `monads' and MonadMinus [Re: Parsers are monadic?]

oleg at pobox.com oleg at pobox.com
Tue Jul 3 07:51:31 EDT 2007

When designing the full Kanren, we have experimented with
two-continuation actions and various plumbing combinators (any, all,
deterministic-all, etc). We eventually gave up on this after we
realized that a simple interface suffices. Called MonadMinus,
it is capable of defining LogicT monad with the true logical
negation as well as interleaving and committed choice. Our ICFP05
paper describes MonadMinus monad (actually, the transformer) and
LogicT as well as their two implementations. One of them uses success
and failure continuations, and the other is based on delimited
continuations. The latter offer an additional way to report
`out-of-band' errors and continue parsing after the error has been


It is fair to say that whereas foldr/build and destroy/unfoldr fusion
techniques work for Haskell lists, msplit/reflect in the LogicT paper
is a fusion law for a general backtracking computation over arbitrary,
perhaps even strict, base monad. That computation may look nothing
like list; in fact, the LogicT paper gives an example with delimited
continuations, with abort playing the role of nil and shift the role
of cons.

More information about the Haskell-Cafe mailing list