User loginNavigation |
Backtracking, Interleaving, and Terminating Monad Transformers
Backtracking, Interleaving, and Terminating Monad Transformers. Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman and Amr Sabry.
We design and implement a library for adding backtracking computations to any Haskell monad. Inspired by logic programming, our library provides, in addition to the operations required by the MonadPlus interface, constructs for fair disjunctions, fair conjunctions, conditionals, pruning, and an expressive top-level interface. Implementing these additional constructs is well-known in models of backtracking based on streams, but not known to be possible in continuation-based models. We show that all these additional constructs can be generically and monadically realized using a single primitive which we call msplit. We present two implementations of the library: one using success and failure continuations; and the other using control operators for manipulating delimited continuations. As you can expect from the author list, this is cool stuff. Enjoy! |
Browse archives
Active forum topics |
Recent comments
5 weeks 5 days ago
5 weeks 5 days ago
5 weeks 5 days ago
11 weeks 5 days ago
52 weeks 10 hours ago
52 weeks 14 hours ago
52 weeks 14 hours ago
1 year 22 weeks ago
1 year 26 weeks ago
1 year 27 weeks ago