## Fair conjunction and disjunction

How can you write a Haskell predicate that detects (without diverging) that both of these two infinite trees are unsorted?

Department of Computing Science, Christian-Albrechts-University of Kiel, Germany

How can you write a Haskell predicate that detects (without diverging) that both of these two infinite trees are unsorted?

Insipred by Monadic Conctraint Programming by Tom Schrijvers et. al., I wrapped up some thoughts on the difference between monadic and queue-based tree search.

When coding my first library for Hackage, I learned about two programming problems and their solutions in Haskell. I boiled them down to the essence and wrote two posts to share them. One on polyvariadic functions, the other on heterogeneous collections. To get an executable Haskell file simply strip off the `.html`

suffix.

I am currently developing a Haskell library for constraint functional-logic programming. It is in an early alpha stage (does not support higher-order functions and implements no constraint solvers) but can already be used to mimic simple lazy functional-logic programs in Haskell.

In order to experiment with constraint monads I have implemented a simple SAT solver based on the Davis-Putnam-Logemann-Loveland (DPLL) algorithm. The marked-up code is meant for human consumption — if you want to execute it, you should fetch the latest version from my git repository.

In a previous post I have explained how to extend arbitrary instances of `MonadPlus`

with constraint solving capabilities. Now, I’ll focus on how to use this functionality to implement lazy non-deterministic computations on top of a `MonadPlus`

.

Recently, I thought about two seemingly different topics which turn out to form a fruitful combination.

One thing I have been thinking about a lot is how to model functional-logic programming in Haskell without using impure features to ensure call-time choice semantics of lazy computations. The other thing is how to integrate constraint solving in a purely functional setting, to improve the performance of test-case generation.

It turns out that a framework for constrained monadic computations is enough to express call-time choice in non-deterministic lazy computations. We can add constraint solving to any instance of the `MonadPlus`

type class and, hence, reuse existing instances of this class to model lazy functional-logic programming in pure Haskell.