# Conjure

Conjure is a tool that produces Haskell functions out of partial definitions.

This is currently an experimental tool in its early stages,
don't expect much from its current version.
It is just a piece of curiosity in its current state.

## Installing

To install the latest Conjure version from Hackage, just run:

```
$ cabal update
$ cabal v1-install code-conjure
```

If you are using Cabal v3.0 or later,
avoid using `cabal install`

for the time being
and use `v1-install`

instead.

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.

## Conjuring functions

Given

```
square :: Int -> Int
square 0 = 0
square 1 = 1
square 2 = 4
```

and

```
primitives :: [Expr]
primitives = [ val (0::Int)
, val (1::Int)
, value "+" ((+) :: Int -> Int -> Int)
, value "*" ((*) :: Int -> Int -> Int)
]
```

running

```
> conjure "square" square primitives
```

yields

```
square :: Int -> Int
-- testing 3 combinations of argument values
-- looking through 3 candidates of size 1
-- looking through 3 candidates of size 2
-- looking through 5 candidates of size 3
square x = x * x
```

in less than a second.

See the `eg/arith.hs`

example.

## Conjuring recursive functions

Given

```
factorial :: Int -> Int
factorial 0 = 1
factorial 1 = 1
factorial 2 = 2
factorial 3 = 6
factorial 4 = 24
factorial 5 = 120
```

and

```
primitives :: [Expr]
primitives = [ val (0::Int)
, val (1::Int)
, value "+" ((+) :: Int -> Int -> Int)
, value "*" ((*) :: Int -> Int -> Int)
, value "dec" (subtract 1 :: Int -> Int)
, value "==" ((==) :: Int -> Int -> Bool)
]
```

running

```
> conjure "factorial" factorial primitives
```

yields

```
factorial :: Int -> Int
-- testing 6 combinations of argument values
-- looking through 3 candidates of size 1
-- looking through 5 candidates of size 2
-- looking through 8 candidates of size 3
-- looking through 26 candidates of size 4
-- looking through 59 candidates of size 5
-- looking through 167 candidates of size 6
-- looking through 581 candidates of size 7
-- looking through 1654 candidates of size 8
-- looking through 5754 candidates of size 9
-- looking through 17797 candidates of size 10
factorial n = if n == 0 then 1 else n * factorial (dec n)
```

in about 3 seconds.

See the `eg/factorial.hs`

example.

It is also possible to generate:

```
factorial n = if n == 0 then 1 else n * factorial (n - 1)
```

in about 90s by including `(-) :: Int -> Int -> Int`

in the primitives.

## Related work

MagicHaskeller (2007) is another tool
that is able to generate Haskell code automatically.
It supports recursion through
catamorphisms, paramorphisms and the fix function.
It is more mature than Conjure and is several orders of magnitude faster.

Barliman for Lisp is another tool that does program synthesis.

There are hundreds of others,
I'll add the most closely related here when I have the time.

## Further reading

For a detailed documentation of each function, see
Conjure's Haddock documentation.

Conjure, Copyright 2021 Rudy Matela,
distribued under the 3-clause BSD license.