Search code examples
listprologpattern-matchingprolog-setof

Using Pattern Matching in Prolog to Find Submultisets


I am new to prolog and I was wondering if anyone could help me with this problem. The problem: given the integers 1,2,3,4, and the predicates mult/2, div/2, div/2, minus/2, and minus/2, and eval/2, I need to write a predicate solutions/1 that, when called like this:

?- solutions(L).

it should terminate with the variable L unified to a list of expressions with value 6. Expressions are of the form:

X, Y, exp/2

But my code is not working. I have two versions. The first freezes up SWI-Prolog, not returning any answer after I type a period, and not letting me evaluate anything else afterward:

eval(1,1.0).
eval(2,2.0).
eval(3,3.0).
eval(4,4.0).

eval(mult(X,Y),Z) :-
    eval(X,A),
    eval(Y,B),
    Z is A*B.

eval(div(X,Y),Z) :-
    eval(X,A),
    eval(Y,B),
    Z is A/B.

eval(minus(X,Y),Z) :-
    eval(X,A),
    eval(Y,B),
    Z is A-B.

solutions(L) :-
    setof(X,eval(X,6),L),
    print(L).

The second version just returns false when I type ?- solutions(L).:

solutions(L) :-
    setof([exp,X,Y],eval(exp(X,Y),6),L),
    print(L).

Thank you so much for taking the time to help!


Solution

  • Maybe you're looking for something like

    solutions(L) :-
        Ns = [1,2,3,4],
        Ex = [*,/,-],
        findall((X,Y,E),
           (member(X,Ns),member(Y,Ns),member(E,Ex),F=..[E,X,Y],6=:=F),
           L).
    

    that yields

    ?- solutions(L).
    L = [(2, 3,  (*)),  (3, 2,  (*))].
    

    Expressions are usually recursive, that is, arguments could be expressions instead of plain numbers. But then, in my opinion your problem is underspecified, as we need criteria to stop the infinite flow of solutions resulting - for instance - by repeated application of operations that don't change the value. Like multiply or divide by 1.