More trouble with prolog list building

Question

I'm sorry to post another question on this, but I just seem to be going in circles here!

For my program I need to make a list of lists, with each sublist containing 2 numbers, X and Y along with the sum and product of these 2 numbers. So far I have the following:

genList(100,N, X,[]).

genList(S,N, X,[[X,Y,Sum,Product]|Xs]):-

    Y is N+1,
    Sum is X+Y,
    NewS is Sum,
    Sum<101,
    Product is X*Y,
    N1 is N+1,
    genList(NewS,N1, X,Xs).

genList(S,N,X,Q):-
    N+X < 101,
    NextX is X + 1,
    genList(0,NextX,NextX,Q).

The goal is to find every pair of numbers where sum<= 100. So running through the above for one starting value, X would find every pair 1 < X < Y, where sum<=100, and running through it with all numbers 2-N would give a complete list of possible pairs.

For those interested, the problem I'm working through is the sum/product problem, described here (Second on the page)

If anyone could help with this it would be greatly appreciated!

Also, no built in prolog predicates are able to be used, hence the complicated way of doing this rather than with a findall.

A small extract of the output produced by this predicate is as follows:

[[5,6,11,30],[5,7,12,35],[5,8,13,40],[5,9,14,45],[5,10,15,50],[5,11,16,55],[5,12,17,60],[5,13,18,65],[5,14,19,70],[5,15,20,75],[5,16,21,80],[5,17,22,85],[5,18,23,90],[5,19,24,95],[5,20,25,100],[5,21,26,105],[5,22,27,110], ...

I think it's very close, but there's still something not quite right.

It cycles through number pairs, but requires the use of ";" to view all the answers, which isn't what I want. Additionally, it returns false after all the answers are exhausted. I just can't figure it out.

Also, it gives a complete answer for the starting value, but then removes a sublist each time until I'm left with only the last set of pairs.

E.g. genList(0,48,48,Q). gives me:

[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[48,52,100,2496]]
[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[48,52,100,2496],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[48,50,98,2400],[48,51,99,2448],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[48,50,98,2400],[49,50,99,2450],[49,51,100,2499]]
[[48,49,97,2352],[49,50,99,2450],[49,51,100,2499]]
[[49,50,99,2450],[49,51,100,2499]]
false.

As you can see, a sublist gets removed each time, I just can't see why!

Answer 1

Well, you're almost there. Since you spent quite some time on this problem already I'll just show you some valid code and comment it:

First we call a worker predicate that'll carry X and Y as arguments and initialize them to 0:

validPair(Result) :-
    validPair(0, 0, Result).

Then we handle our base case. Since we started from 0, the base case is the upper bound. We could have went the other way around, it's just a choice really. Note that the cut here means that we won't have to worry about Y being superior to 100 in our following clauses since they won't be executed in that case.

validPair(_X, 101, []) :- !.

Here is now the case where X fits the correct limits for the sum to be under 100. We first check that everything is ok and then we use the !/0 predicate to once more prevent the execution to reach our last clause since that wouldn't make sense. After it's done we just avec to calculate the interesting values and add them to the list.

validPair(X, Y, [[X, Y, Sum, Product]|R]) :-
    Limit is min(100 - Y, Y),
    X =< Limit,
    !,
    Sum is X + Y,
    Product is X * Y,
    NextX is X + 1,
    validPair(NextX, Y, R).

The only case left to handle is when X goes above the limit we fixed so that the sum is under 100. When that happens we start again with the next Y and reset X to 0.

validPair(_X, Y, R) :-
    NextY is Y + 1,
    validPair(0, NextY, R).

If anything troubles you please ask for clarification in comments.

Note: the cuts used here are red cuts - ie the correctness of the predicate totally depends on the order of the clauses. It's bad practise. Try to supplement them with proper guards (like X =< 100 for example), it'd be a good addition :)

Edit:

Now let's audit your code :D I'll start by commenting on the style: In this clause (called fact since it has no body), you use N and X only once ie you do not care about storing their value. In this case, we prefix their name with a _ or just use the anonymous variable _:

genList(100,N, X,[]).

turns into

genList(100, _N, _X, []).

or

genList(100, _, _, []).

Same thing here with S. It's not used in this clause. It's only used in the first one. You can replace it by _ or _Sum if you want to document its use in the other clause here too (good practise). Then, you use two variables to hold the exact same value. It has no interest here. Just call your next genList/4 with Sum as first argument instead of declaring a new variable just for that. Same thing with Y and N1. A proper version of this clause turns:

genList(S,N, X,[[X,Y,Sum,Product]|Xs]):-
    Y is N+1,
    Sum is X+Y,
    NewS is Sum,
    Sum<101,
    Product is X*Y,
    N1 is N+1,
    genList(NewS,N1, X,Xs).

into

genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

Your last clause has an issue with arithmetic: N + X is just the term +(N, X). It's not the value N + X. You have to use the is/2 predicate just as in your other clauses. Same issue as the second clause for S. Those little edits turn:

genList(S,N,X,Q):-
    N+X < 101,
    NextX is X + 1,
    genList(0,NextX,NextX,Q).

into

genList(_PreviousSum, N, X, Q) :-
    Sum is N + X,
    Sum < 101,
    NextX is X + 1,
    genList(0, NextX, NextX, Q).

So, at the moment your corrected program looks like:

genList(100, _N, _X, []).
genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).
genList(_PreviousSum, N, X, Q) :-
    Sum is N + X,
    Sum < 101,
    NextX is X + 1,
    genList(0, NextX, NextX, Q).

Since it was just style edits, it doesn't change its behavior.

Now let's look at what was wrong about it, not in the style, but in the logic. First, the base case. Here everything is fine. You check for the sum being your upper bound and if it is return []. Perfect!

genList(100, _N, _X, []).

Now, your "inner recursion". It's almost fine. Let's look at the detail that bugs me: you have a value that holds your previous sum, but compute a new one and retest it against the upper bound + 1. a better idea would be to test PreviousSum against < 100 and to remove the Sum < 101 test. It'd better justify the fact that you have an argument just for that! Plus it's more understandable that it's guard being used to prevent execution of the clause in that limit case. So,

genList(_PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    Y is N+1,
    Sum is X + Y,
    Sum<101,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

would turn into

genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

Note that this modification is kinda stylistic, it doesn't modify the program behavior. It's still makes it way more readable though!

Now, the big bad wolf: genList(_PreviousSum, N, X, Q) :- Sum is N + X, Sum < 101, NextX is X + 1, genList(0, NextX, NextX, Q). Many things to say here. First and once again, you do not need to compute Sum since PreviousSum already holds the value. Then, it should be tested for < 100 instead of < 101. Then, it should be tested that X >= N, because that's only in that case that you do not want to go through your second clause but in this one instead. And last but not least, instead of starting a new iteration with genList(0, NextX, NextX, Q) you should start it with genList(NextX, 0, NextX, Q). Here you didn't reset properly the values. The resulting clause is:

genList(PreviousSum, N, X, Q) :-
    PreviousSum < 100,
    N >= X,
    NextX is X + 1,
    genList(NextX, 0, NextX, Q).

As you saw, we know formalized that we can't go through our second clause if N >= X. We should add to it the proper test to be assured that it's correct:

genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    N < X,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).

Here you're done, your program is correct!

Final version is:

genList(100, _N, _X, []).
genList(PreviousSum, N, X,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    N < X,
    Y is N+1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, Y, X, Xs).
genList(PreviousSum, N, X, Q) :-
    PreviousSum < 100,
    N >= X,
    NextX is X + 1,
    genList(NextX, 0, NextX, Q).

The variable naming is still poor. A clearer version would be:

genList(100, _X, _Y, []).
genList(PreviousSum, X, Y,[[X, Y, Sum, Product]|Xs]):-
    PreviousSum < 100,
    X < Y,
    NewX is X + 1,
    Sum is X + Y,
    Product is X * Y,
    genList(Sum, NewX, Y, Xs).
genList(PreviousSum, X, Y, Q) :-
    PreviousSum < 100,
    X >= Y,
    NextY is Y + 1,
    genList(NextY, 0, NextY, Q).

Here you still have a problem (yeah it nevers ends :D): the fact that you increment your variables BEFORE calculating the sum product etc means that you skip some values. Try to increment after. It's let as an exercise :)