A Generic ’solve’ Predicate

The examples of state space searching described previously have all been tailored to a particular problem — the algorithms have been general, but the implementation has included type signatures specific to the problem, e.g.:

:- type block ---> a; b; c.
:- type stack == list(block).
:- type situation == list(stack).
:- type solution == list(situation).
:- pred solve(situation::in, solution::out) is nondet.

It would be convenient if we could write a ’solve’ predicate which would work with any problem, stated correctly.

To do this we will parameterise ’solve’ by the type of the nodes in the state space (i.e. block in the example above), and make the predicates which define our goal and produce our successors into parameters passed to ’solve’.

This gives us the Mercury interface:

:- interface.
:- import_module list.

    /* the type of the successor predicate to be used by the solve predicate */
:- type succ_pred(T) == pred(T, T).
:- inst succ_pred == (pred(in,out) is nondet).
:- mode succ_pred_in == in(succ_pred).
    /* the type of the goal predicate to be used by the solve predicate */
:- type goal_pred(T) == pred(T).
:- inst goal_pred == (pred(in) is semidet).
:- mode goal_pred_in == in(goal_pred).

:- pred solve(succ_pred(T)::succ_pred_in, goal_pred(T)::goal_pred_in, T::in, list(T)::out) is nondet.

And our predicates for searching for a path in a directed graph are defined like this:

:- type node ---> a; b; c; d; e; f; g.
:- pred s `with_type` succ_pred(node) `with_inst` succ_pred.
s(a,b).
...
s(e,g).

:- pred goal `with_type` goal_pred(node) `with_inst` goal_pred.
goal(Situation) :-
    Situation = g.

The complete source code for the two modules is below the fold.

:- module solve.
:- interface.
:- import_module list.

:- type succ_pred(T) == pred(T, T).
:- inst succ_pred == (pred(in,out) is nondet).
:- mode succ_pred_in == in(succ_pred).

:- type goal_pred(T) == pred(T).
:- inst goal_pred == (pred(in) is semidet).
:- mode goal_pred_in == in(goal_pred).

:- pred solve(succ_pred(T)::succ_pred_in, goal_pred(T)::goal_pred_in, T::in, list(T)::out) is nondet.

:- implementation.
:- import_module solutions.
:- import_module io.

solve(Succ, Goal, Start, Solution) :-
    breadthfirst(Succ, Goal, [[Start]], Solution). 

:- pred breadthfirst(succ_pred(T)::succ_pred_in, goal_pred(T)::goal_pred_in, list(list(T))::in, list(T)::out) is nondet.
breadthfirst(_, Goal, [[Node | Path] | _], [Node | Path]) :-
    call(Goal,Node).

breadthfirst(Succ, Goal, [Path | Paths], Solution) :-
    trace [io(!IO)] (io.write_list([Path | Paths], "---\n", io.print, !IO),
        io.nl(!IO)),
    extend(Succ, Path, NewPaths),
    append(Paths, NewPaths, Paths1),
    breadthfirst(Succ, Goal, Paths1, Solution).

:- pred extend(succ_pred(T)::succ_pred_in,list(T)::in,list(list(T))::out) is semidet.
extend(Succ, [Node | Path], NewPaths) :-
    solutions(
        pred(X::out) is nondet :- 
        (
            X = [NewNode, Node | Path],
            call(Succ, Node, NewNode),
            not member(NewNode, [Node | Path])
        ),
        NewPaths).

:- module graphsolve.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is cc_multi.
:- implementation.
:- import_module solve.
:- import_module list.

:- type node ---> a; b; c; d; e; f; g.
:- pred s `with_type` succ_pred(node) `with_inst` succ_pred.
s(a,b).
s(a,c).
s(b,d).
s(b,e).
s(d,f).
s(e,g).

:- pred goal `with_type` goal_pred(node) `with_inst` goal_pred.
goal(Situation) :-
    Situation = g.

main(!IO) :-
    if solve(s,goal,a,S) then
        reverse(S,S1), print(S1,!IO)
    else
        print("Failed\n",!IO).

One Trackback

  1. By My Diversions » Blog Archive » Escape from Zurg on September 2, 2007 at 4:06 am

    [...] My Diversions Notes on things I’m thinking and doing « A Generic ’solve’ Predicate [...]

Post a Comment

Your email is never shared. Required fields are marked *

*
*