logict is a “continuation-based, backtracking, logic programming monad”. It is a library that provides backtracking computations to a Haskell monad. It is now available on Fedora. Install it using:

 $ sudo yum install ghc-logict-devel

The observeAll function, for example, obtains all the results from a Logic computation:

import Control.Applicative ((<|>))
import Control.Monad.Logic (observeAll)
import Control.Monad (filterM)

powerset :: [a] -> [[a]]
powerset = observeAll . filterM (const (return False <|> return True))

You can compile and run the above example using:

~~~~ {.shell} $ ghci Powerset.hs GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim … linking … done. Loading package integer-gmp … linking … done. Loading package base … linking … done. [1 of 1] Compiling Main ( Powerset.hs, interpreted ) Ok, modules loaded: Main.

*Main> powerset [1,2] Loading package transformers-0.2.2.0 … linking … done. Loading package mtl-2.0.1.0 … linking … done. Loading package logict-0.5.0.1 … linking … done. [[],[2],[1],[1,2]] ~~~~