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

Post a Comment

Your email is never shared. Required fields are marked *