Pairing Two Lists

Question

Hey guys, a few simple prolog questions that I'm hoping you can help me on. Basically, I am trying to write a function that takes input as two lists, and an integer. From there, the function will try to find an x in the first list and a y in the second list such that x + y is equal to the input integer.

So far I am thinking to just recurse down by doing something such as follows:

sum([H1|T1], [H2|T2], Value) :-
    NewVal is H1+H2
    % Check for equality?
    sum(List1, T2, Value)
    sum(T1, List2, Value).

So, a few questions regarding this method.

1) How do I refer the the "whole" list after I've passed it in as H1|T1? In the example I just named them List1 and List2 for reading ease.

2) I can check for equality, but how do I "stop" searching and force output?

Answer 1

1. IIRC, I think you should be able to pass the whole list as a parameter using [H1|T1].
2. Most likely you would want to use the Prolog cut, which stops searching for solutions.

Answer 2

You need a disjunction, not a conjunction: EITHER h1+h2 is ok, OR there is a solution without h1, OR there is a solution without h2.

There are two syntaxes in prolog for disjunction. You can use a semicolon:

sum([H1|T1], [H2|T2], Value) :- Value is H1+H2 ; sum([H1|T1], T2, Value) ; sum(T1, [H2|T2], Value).

Or you can use separate clauses:

sum([H1|_], [H2|_], Value) :- Value is H1+H2.
sum([H1|T1], [_|T2], Value) :- sum([H1|T1], T2, Value).
sum([_|T1], [H2|T2], Value) :- sum(T1, [H2|T2], Value).

Answer 3

1) Kaleb is right, to do this, just reconstruct the list as the head cons with the tail.
2) Jerome is right, but here's another way of putting it...

Your question "How do I make it stop?" actually hints at a missing part of your predicate. You currently have a recursive predicate with no base case - the recursion has no way of being able to stop. Well I guess in this case it will get to the end of one of the lists, but since this will then be the empty list it will then fail when being unified with the term [H|T] as there is no head item.

When writing a recursive predicate that is looking for a particular element of a list it is common to make the base contain the constraints which define the solution. You can see this in Jerome's solution. This results in a predicate that succeeds once it has found a solution and doesn't continue to process the list afterwards. It will however continue on after this point if you tell it to backtrack and look for more solutions. If you don't care about these further solutions, then you can use the cut to discard them.