What do you think about Mercury?

[Fergus Henderson]

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.