Escape from Zurg

This Lambda the Ultimate post links to a paper which compares writing a search algorithm in Prolog and Haskell, and notes that Haskell’s strong typing makes the task easier. While the paper mentions several embeddings of logic programming into functional languages it doesn’t mention Mercury.

I was able to easily create successor and goal predicates for this problem which work with the breadth first searching predicate I wrote earlier. Note that there is one significant shortcoming in my implementation — because I use lists where I should be using sets in the representation of nodes in my search space, nodes which should be equal are not, so the search takes far longer than it should. But it makes the point that Mercury’s discriminated unions and type system give a Prolog-like language the same benefit which Haskell’s type system gives a functional one.

The code for the solve client follows:

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

:- type actor ---> buzz; woody; rex; hamm.
:- type torchPos ---> left; right.
:- type escapeState ---> escapeState(inZurg :: list(actor), crossed :: list(actor), batteryCharge :: int, torch :: torchPos).
:- pred s `with_type` succ_pred(escapeState) `with_inst` succ_pred.
s(escapeState(In1, Out1, Charge1, left), escapeState(In2, [C1, C2 | Out1],Charge2, right)) :-
    delete(In1, C1, In1WithoutC1),
    delete(In1WithoutC1, C2, In2),
    cost(C1,C1Cost),
    cost(C2,C2Cost),
    Cost = int.max(C1Cost,C2Cost),
    Charge2 = int.minus(Charge1,Cost),
    Charge2 >= 0.

s(escapeState(In1, Out1, Charge1, right), escapeState([C1 | In1], Out2,Charge2,left)) :-
        delete(Out1, C1, Out2),
        cost(C1,Cost),
        Charge2 = int.minus(Charge1,Cost),
        Charge2 >= 0.

:- pred cost(actor::in, int::out) is det.
cost(buzz, 5).
cost(woody, 10).
cost(rex, 20).
cost(hamm, 25).


:- pred goal `with_type` goal_pred(escapeState) `with_inst` goal_pred.
goal(escapeState([],_,_,right)).

main(!IO) :-
    if solve(s,goal,escapeState([buzz,woody,rex,hamm],[],60,left),S) then
        reverse(S,S1), print(S1,!IO)
    else
        print("Failed\n",!IO).

Post a Comment

Your email is never shared. Required fields are marked *

*
*