Conjure

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 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.

Program synthesis within Haskell.

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 (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 (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 (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.