Conjure
=======
[![Conjure's Build Status][build-status]][build-log]
[![Conjure on Hackage][hackage-version]][code-conjure-on-hackage]
[![Conjure on Stackage LTS][stackage-lts-badge]][code-conjure-on-stackage-lts]
[![Conjure on Stackage Nightly][stackage-nightly-badge]][code-conjure-on-stackage-nightly]
![Conjure logo][conjure-logo]
Conjure is a tool that synthesizes Haskell functions out of partial definitions.
Installing
----------
To install the [latest Conjure version from Hackage], just run:
$ cabal update
$ cabal install code-conjure
Prerequisites are [express], [leancheck] and [speculate].
They should be automatically resolved and installed by [Cabal].
NOTE: the name of the Hackage package is __[`code-conjure`]__
-- not to be confused with [Conjure the BitTorrent client].
Starting from Cabal v3.0, you need to pass `--lib` as an argument to
`cabal install` to install packages globally on the `default` user environment:
$ cabal install code-conjure --lib
If you already have Conjure installed
[Cabal may refuse to update](https://github.com/haskell/cabal/issues/7373)
to the latest version.
To update, you need to reset your user's cabal installation with:
rm -rf ~/.cabal/{bin,lib,logs,share,store} ~/.ghc/*/
WARNING: the above command will erase all user-local packages.
Synthesizing functions
----------------------
To use Conjure, import the library with:
import Conjure
Then, declare a partial definition of a function to be synthesized.
For example,
here is a partial implementation of a function that computes the factorial of a number:
factorial :: Int -> Int
factorial 1 = 1
factorial 2 = 2
factorial 3 = 6
factorial 4 = 24
Next, declare a list of ingredients that seem like interesting pieces
in the final fully-defined implementation.
For example,
here is a list of ingredients including
addition, multiplication, subtraction and their neutral elements:
ingredients :: [Ingredient]
ingredients = [ unfun (0::Int)
, unfun (1::Int)
, fun "+" ((+) :: Int -> Int -> Int)
, fun "*" ((*) :: Int -> Int -> Int)
, fun "-" ((-) :: Int -> Int -> Int)
]
Finally, call the [`conjure`] function,
passing the function name, the partial definition and the list of ingredients:
factorial :: Int -> Int
-- 0.1s, testing 4 combinations of argument values
-- 0.8s, pruning with 27/65 rules
-- 0.8s, 3 candidates of size 1
-- 0.9s, 3 candidates of size 2
-- 0.9s, 7 candidates of size 3
-- 0.9s, 8 candidates of size 4
-- 0.9s, 28 candidates of size 5
-- 0.9s, 35 candidates of size 6
-- 0.9s, 167 candidates of size 7
-- 0.9s, tested 95 candidates
factorial 0 = 1
factorial x = x * factorial (x - 1)
Conjure is able to synthesize the above implementation in less than a second
in a regular laptop computer.
It is also possible to generate a folding implementation
like the following:
factorial x = foldr (*) 1 [1..x]
by including [`enumFromTo`] and [`foldr`] in the background.
For more information, see the `eg/factorial.hs` example and
the Haddock documentation for the [`conjure`] function.
Synthesizing functions over algebraic data types
------------------------------------------------
Conjure is not limited to integers,
it works for functions over algebraic data types too.
Consider the following partial definition of `take`:
take' :: Int -> [a] -> [a]
take' 0 [x] = []
take' 1 [x] = [x]
take' 0 [x,y] = []
take' 1 [x,y] = [x]
take' 2 [x,y] = [x,y]
take' 3 [x,y] = [x,y]
Conjure is able to find an appropriate implementation
given list constructors, zero, one and subtraction:
> conjure "take" (take' :: Int -> [A] -> [A])
> [ unfun (0 :: Int)
> , unfun (1 :: Int)
> , unfun ([] :: [A])
> , fun ":" ((:) :: A -> [A] -> [A])
> , fun "-" ((-) :: Int -> Int -> Int)
> ]
take :: Int -> [A] -> [A]
-- 0.2s, testing 153 combinations of argument values
-- 0.2s, pruning with 4/7 rules
-- ... ... ... ... ...
-- 0.4s, 5 candidates of size 9
-- 0.4s, tested 15 candidates
take 0 xs = []
take x [] = []
take x (y:xs) = y:take (x - 1) xs
The above example also takes less than a second to run in a modern laptop.
The selection of functions in the list of ingredients was minimized
to what was absolutely needed here.
With a larger collection as ingredients YMMV.
Synthesizing from specifications (for advanced users)
-----------------------------------------------------
Conjure also supports synthesizing from a functional specification
with [`conjureFromSpec`].
Consider a function `duplicates` that given a list of values
should return all values that are repeated.
The resulting list should itself not contain repetitions.
Even an experienced programmer
may take a few minutes to come up with a correct definition for `duplicates`
even when told that a conditional definition
is possible using only
`[]`,
`:`,
`not`,
`&&` and
`elem`.
(We invite the reader to try.)
We can encode a specification of duplicates with test properties like so:
duplicatesSpec :: ([Int] -> [Int]) -> [Property]
duplicatesSpec duplicates = and
[ property $ \x xs -> (count (x ==) xs > 1) == elem x (duplicates xs)
, property $ \x xs -> count (x ==) (duplicates xs) <= 1
] where count p = length . filter p
Conjure finds a solution in 1 second
with the following call:
conjureFromSpec "duplicates" duplicatesSpec
[ unfun ([] :: [Int])
, fun "not" not
, fun "&&" (&&)
, fun ":" ((:) :: Int -> [Int] -> [Int])
, fun "elem" (elem :: Int -> [Int] -> Bool)
, guard -- allows guards
]
This is the definition produced by Conjure:
duplicates [] = []
-- 0.2s, pruning with 21/26 rules
-- 0.2s, 2 candidates of size 1
-- 0.3s, 1 candidates of size 2
-- 0.3s, 0 candidates of size 3
-- 0.3s, 2 candidates of size 4
-- 0.3s, 1 candidates of size 5
-- 0.3s, 2 candidates of size 6
-- 0.3s, 3 candidates of size 7
-- 0.3s, 8 candidates of size 8
-- 0.3s, 13 candidates of size 9
-- 0.3s, 18 candidates of size 10
-- 0.3s, 21 candidates of size 11
-- 0.3s, 28 candidates of size 12
-- 0.3s, 39 candidates of size 13
-- 0.4s, 54 candidates of size 14
-- 0.5s, 67 candidates of size 15
-- 0.7s, 80 candidates of size 16
-- 1.0s, 99 candidates of size 17
-- 1.0s, tested 340 candidates
duplicates (x:xs)
| elem x xs && not (elem x (duplicates xs)) = x:duplicates xs
| otherwise = duplicates xs
Related work
------------
__Conjure's dependencies__.
Internally, Conjure uses [LeanCheck], [Speculate] and [Express].
[LeanCheck] does testing similarly to [QuickCheck], [SmallCheck] or [Feat].
[Speculate] discovers equations similarly to [QuickSpec].
[Express] encodes expressions involving [Dynamic] types.
[Speculate]: https://github.com/rudymatela/speculate
[Express]: https://github.com/rudymatela/express
[QuickCheck]: https://hackage.haskell.org/package/QuickCheck
[smallcheck]: https://hackage.haskell.org/package/smallcheck
[Feat]: https://hackage.haskell.org/package/testing-feat
[QuickSpec]: https://hackage.haskell.org/package/quickspec
[Dynamic]: https://hackage.haskell.org/package/base/docs/Data-Dynamic.html
__Program synthesis within Haskell.__
[MagicHaskeller]: https://hackage.haskell.org/package/MagicHaskeller
[Igor II]: https://cogsys.uni-bamberg.de/projects/effalip
[MagicHaskeller] (2007) is another tool
that is able to generate Haskell code automatically.
It supports recursion through
catamorphisms, paramorphisms and the [`fix`] function.
[Igor II] (2010) is able to synthesize Haskell
programs as well.
[Hoogle]: https://hoogle.haskell.org/
[Hoogle+]: https://hoogleplus.goto.ucsd.edu/
[Hoogle] (2004) is a search engine for Haskell functions.
It is not able to synthesize expressions
but it can find functions that match a type.
[Hoogle+] (2020) is similar to Hoogle
but is able to search for small expressions.
In addition to the type, Hoogle+ allows
users to provide tests that the function should pass.
__Program synthesis beyond Haskell.__
[PushGP]: https://github.com/lspector/Clojush
[G3P]: https://github.com/t-h-e/HeuristicLab.CFGGP
[PushGP] (2002) and [G3P] (2017) are genetic programming systems
that are able to synthesize programs in Push and Python respectively.
Differently from Conjure or MagicHaskeller,
they require around a hundred tests for traning
instead of just about half a dozen.
[Barliman]: https://github.com/webyrd/Barliman
[Barliman] (2016) for Lisp is another tool that does program synthesis.
Further reading
---------------
For a detailed documentation of each function, see
[Conjure's Haddock documentation].
The `eg` folder in the source distribution
contains more than 60 examples of use.
Conjure, Copyright 2021-2025 Rudy Matela,
distribued under the 3-clause BSD license.
[Conjure's Haddock documentation]: https://hackage.haskell.org/package/code-conjure/docs/Conjure.html
[`conjure`]: https://hackage.haskell.org/package/code-conjure/docs/Conjure.html#v:conjure
[`conjureFromSpec`]: https://hackage.haskell.org/package/code-conjure/docs/Conjure.html#v:conjureFromSpec
[`foldr`]: https://hackage.haskell.org/package/base/docs/Prelude.html#v:foldr
[`enumFromTo`]: https://hackage.haskell.org/package/base/docs/Prelude.html#v:enumFromTo
[`fix`]: https://hackage.haskell.org/package/base/docs/Data-Function.html#v:fix
[`holds`]: https://hackage.haskell.org/package/leancheck/docs/Test-LeanCheck.html#v:holds
[symbol `>`]: https://www.haskell.org/haddock/doc/html/ch03s08.html#idm140354810780208
[Template Haskell]: https://wiki.haskell.org/Template_Haskell
[conjure-logo]: https://github.com/rudymatela/conjure/raw/master/doc/conjure.svg?sanitize=true
[`code-conjure`]: https://hackage.haskell.org/package/code-conjure
[Conjure the BitTorrent client]: https://hackage.haskell.org/package/conjure
[Cabal]: https://www.haskell.org/cabal
[Haskell]: https://www.haskell.org/
[leancheck]: https://hackage.haskell.org/package/leancheck
[LeanCheck]: https://hackage.haskell.org/package/leancheck
[express]: https://hackage.haskell.org/package/express
[speculate]: https://hackage.haskell.org/package/speculate
[avoid using `cabal install`]: https://github.com/haskell/cabal/issues/7373
[latest Conjure version from Hackage]: https://hackage.haskell.org/package/code-conjure
[build-log]: https://github.com/rudymatela/conjure/actions/workflows/build.yml
[build-status]: https://github.com/rudymatela/conjure/actions/workflows/build.yml/badge.svg
[hackage-version]: https://img.shields.io/hackage/v/code-conjure.svg
[code-conjure-on-hackage]: https://hackage.haskell.org/package/code-conjure
[stackage-lts-badge]: https://stackage.org/package/code-conjure/badge/lts
[stackage-nightly-badge]: https://stackage.org/package/code-conjure/badge/nightly
[code-conjure-on-stackage]: https://stackage.org/package/code-conjure
[code-conjure-on-stackage-lts]: https://stackage.org/lts/package/code-conjure
[code-conjure-on-stackage-nightly]: https://stackage.org/nightly/package/code-conjure