Depth First Search in Mercury

I’m working through Bratko’s “Prolog Programming for Artificial Intelligence” rewriting the examples in Mercury.This series of posts will be my notes on the changes I needed to make to make these programs work.Page 243-244, defining successor states for stacks of blocks and performing a depth first search. Note that it’s a naive depth first search assuming no cycles.

``````
:- module stacks.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
:- implementation.
:- import_module list.
:- import_module bool.

/*
* In Mercury we can use types to represent the problem domain -- a situation
* is a number of stacks of blocks.
*/
:- type block ---> a; b; c.
:- type stack == list(block).
:- type situation == list(stack).
:- type solution == list(situation).

:- pred s(situation, situation).
:- mode s(in,out) is nondet.

/*
* list.delete uses a different order of arguments to the del predicate
* used by bratko: delete(List, Element, Remainder)
*/
s(Stacks, [Stack1, [Top1 | Stack2] | OtherStacks]) :-
delete(Stacks, [Top1 | Stack1], Stacks1),
delete(Stacks1, Stack2, OtherStacks).

:- pred goal(situation::in) is semidet.
goal(Situation) :-
member([a,b,c], Situation).

:- pred solve(situation::in, solution::out) is nondet.
solve(N, [N]) :- goal(N).
solve(N, [N | Sol1]) :-
s(N, N1),
solve(N1, Sol1).

``````main(!IO) :-
if solve([[c,b,a],[],[]],S) then
print(S,!IO)
else
print("Failed\n",!IO).
``````