A backtracking logic-programming monad.
|Version on this page:||0.7.1.0|
|LTS Haskell 20.23:||0.8.0.0|
|Stackage Nightly 2023-05-28:||0.8.0.0|
|Latest on Hackage:||0.8.1.0|
Module documentation for 0.7.1.0
Provides support for logic-based evaluation. Logic-based programming uses a technique known as backtracking to consider alternative values as solutions to logic statements, and is exemplified by languages such as Prolog and Datalog.
Logic-based programming replaces explicit iteration and sequencing code with implicit functionality that internally “iterates” (via backtracking) over a set of possible values that satisfy explicitly provided conditions.
This package adds support for logic-based programming in Haskell using
the continuation-based techniques adapted from the paper
Backtracking, Interleaving, and Terminating Monad Transformers
by Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, Amr Sabry.
This paper extends previous research into using
mplus is used to specify value alternatives
for consideration and
mzero use used to specify the lack of any
acceptable values—to add support for fairness and pruning using a
set of operations defined by a new
In a typical example for Prolog logic programming, there are a set of facts (expressed as unconditional statements):
parent(sarah, john). parent(arnold, john). parent(john, anne).
and a set of rules that apply if their conditions (body clause) are satisfied:
grandparent(Person, Grandchild) :- parent(Person, X), parent(X, Grandchild).
Execution of a query for this rule
grandparent(G, anne) would result in the following “values”:
grandparent(sarah, anne). grandparent(arnold, anne).
For this query execution,
X are “free” variables where
Grandchild has been fixed to
anne. The Prolog engine internally
“backtracks” to the
parent(Person, X) statement to try different
known values for each variable, executing forward to see if the values
satisfy all the results and produce a resulting value.
Haskell logict Package
The Haskell equivalent for the example above, using the
might look something like the following:
import Control.Applicative import Control.Monad.Logic parents :: [ (String, String) ] parents = [ ("Sarah", "John") , ("Arnold", "John") , ("John", "Anne") ] grandparent :: String -> Logic String grandparent grandchild = do (p, c) <- choose parents (c', g) <- choose parents guard (c == c') guard (g == grandchild) pure p choose = foldr ((<|>) . pure) empty main = do let grandparents = observeAll (grandparent "Anne") putStrLn $ "Anne's grandparents are: " <> show grandparents
In this simple example, each of the
choose calls acts as a
backtracking choice point where different entries of the
array will be generated. This backtracking is handled automatically
MonadLogic instance for
Logic and does not need to be
explicitly written into the code. The
observeAll function collects
all the values “produced” by
Logic, allowing this program to
Anne's grandparents are: ["Sarah","Arnold"]
This example is provided as the
grandparents executable built by the
logict package so you can run it yourself and try various
The example above is very simplistic and is just a brief introduction
into the capabilities of logic programming and the
logict package provides additional functionality such as:
Fair conjunction and disjunction, which can help with potentially infinite sets of inputs.
LogicTmonad stack that lets logic operations be performed along with other monadic actions (e.g. if the parents sample was streamed from an input file using the
MonadLogicclass which allows other monads to be defined which provide logic programming capabilities.
The implementation in this
logict package provides the backtracking
functionality at a lower level than that defined in the associated
paper. The backtracking is defined within the
Alternative class as
empty, whereas the paper uses the
MonadPlus class and
mzero functions; since
Alternative is a
requirement (constraint) for
MonadPlus, this allows both
nomenclatures to be supported and used as appropriate to the client
More details on using this package as well as other functions (including fair conjunction and disjunction) are provided in the Haddock documentation.
- Improve documentation.
- Relax superclasses of
- Support GHC 9.0.
MonadReader r (LogicT m)instance again.
- Remove unlawful
MonadLogic (Writer T w m)instances.
MonadReader r (LogicT m)instance.
- Comply with MonadFail proposal.