What do you think about Mercury?

Fergus Henderson fjh@cs.mu.oz.au
Mon, 9 Apr 2001 14:30:01 +1000

```On 08-Apr-2001, Terrence Brannon <princepawn@earthlink.net> wrote:
>
> 1- Haskell is a pure functional language, but I don't see any support
> for backtracking or other logic features... but my guess is you have
> some way of handling this? How?

The usual way of handling backtracking in Haskell is using lazy lists.
See Phil Wadler's 1985 paper [1].

For an example of this, I've attached a program for solving the
8-queens problem; you can compare this one with the Mercury version
in tests/benchmarks/queens.m in the mercury-tests distribution.
(Probably neither this one nor the Mercury one are ideal style,
but I happened to have them lying around...)

So backtracking is really not that hard to emulate in a lazy functional
language.  Supporting logic variables and constraint solving is a lot
more cumbersome, however.

References
[1] Philip Wadler: How to Replace Failure by a List of Successes: A
method for exception handling, backtracking, and pattern matching in
lazy functional languages. FPCA 1985: 113-128

-- main = print_all_solns 8
main = print_soln_count 9

print_soln_count :: Int -> IO ()
print_soln_count n = putStrLn (show (length (solutions n)))

print_all_solns :: Int -> IO ()
print_all_solns n = sequence (map show_soln (solutions n))

solutions :: Int -> [[Int]]
solutions n = queens (start n)

show_soln :: Show a => a -> IO ()
show_soln soln = putStrLn (show soln)

start :: Int -> [Int]
start n = [1 .. n]

queens :: [Int] -> [[Int]]
queens start_posn = [ posn | posn <- qperm start_posn, safe posn ]

qperm :: [t] -> [[t]]
qperm [] = [[]]
qperm (x:xs) = [(y:zs) | zs <- qperm ys, (y,ys) <- qdelete (x:xs) ]

qdelete :: [t] -> [(t,[t])]
qdelete [] = []
qdelete (x:xs) = ((x,xs) : [ (y,(x:ys)) | (y,ys) <- qdelete xs ])

safe :: [Int] -> Bool
safe [] = True
safe (n:l) = nodiag n 1 l && safe l

nodiag :: Int -> Int -> [Int] -> Bool
nodiag _ _ [] = True
nodiag b d (n:l) = d /= n - b && d /= b - n && nodiag b (d+1) l

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
|  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

```