Prolog - recursive list building

Question

for a program I'm writing I need to make a list of lists, with pairs of numbers representing a product and sum of 2 given numbers.

For now I have a function which I can specify how many times I want to add a list to the list, which will be expanded with the full functionality later.

Here's what I have:

s1(0, X).
s1(Q, X) :-
    N is Q - 1,
    multiply(2, 3, Y),
    A = Y ,
    add(2, 3, Z),
    B = Z,
    addToEnd([A], [B], X),
    s1(N,X).

multiply(A, B, C):-
    C is A * B.

add(A, B, C) :-
    C is A + B.

addToEnd([], L, L).
addToEnd([H|T], L2, [H|L3]) :-
    addToEnd(T, L2, L3).

However, when I run s1(2,X) for example, I get [6,5] returned, then nothing else, it just hangs. When I run s1(0,X), i get true, then false when I hit ;

Can anyone help me with this? I can't see what I'm doing wrong, I feel like it should work!

To clarify how I feel this should work: I call s1(2,X). N = 1, [6,5] added to list in X([[6,5]]) s1(1,X). N=0, [6,5] added to the list in X ([[6,5],[6,5]]) s1(0,X). X = [[6,5],[6,5]]

Answer 1

So, there are many things to say here. First and foremost, as in most declarative languages, a variable cannot really change value.

What that means is that X = 1. will unify 1 to X as you'd expect, but if you add X = 2. after that in your query (X = 1, X = 2.), Prolog will say false. The reason behind that is that you cannot unify 1 with 2 and that X has truly become 1, therefore X cannot be unified to 2.

Though, and that differs from Haskell, Ocaml and the like, you can bind partially a variable, as in X = h(Y).. You'll then be able to further unify it X = h(a(Z))., while you couldn't in the languages mentionned earlier (where a variable is really just an alias for a value).

Why does he tell me all that you wonder? Well, that's your main problem here. You first bind X to [6, 5], and then expect to further bind it to some other things. Once a variable is ground (ie does not contain any free variable inside itself), you cannot ever change its value again.

So here your recursion won't do anything but eventually prove X false. Here it doesn't however since you end up calling addToEnd/3 with the same arguments each time ([6], [5] and [6, 5]).

That being said, let's look at how we could improve your code.

First, a remark:

multiply(2, 3, Y),
A = Y ,
add(2, 3, Z),
B = Z,
addToEnd([A], [B], X),

can be written

multiply(2, 3, Y),
add(2, 3, Z),
addToEnd([Y], [Z], X),

without any loss of information since you do not use A and B again.

Now, let's forget about addToEnd/3 for a moment and think about what you want.

If you enter s1(0, Q), do you really want Q to stay free? Because that's what you state at the moment. It'd make more sense to bind Q to [] in that case. Plus, that'll make a good recursive base case as you'll soon see.

s1(0, []).

is a shortcut to say

s1(0, Q) :- Q = [].

since Prolog does unification in clause heads (the part before :-).

Then, I'll cheat a little but it'll just be to stay clear. You could state that when going from s1(4, Q) to s1(5, Q) you expect Q to hold one more value of some calculus.

Here, we could state that as follows:

s1(N, [SomeCalculus|Q]) :-
    PreviousN is N - 1,
    s1(PreviousN, Q).

Now, we just have to give a value to SomeCalculus:

s1(N, [SomeCalculus|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    SomeCalculus = [X, Y],
    s1(PreviousN, Q).

or, if you followed correctly, we could directly write:

s1(N, [[X, Y]|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

So the complete program would be:

s1(0, []).
s1(N, [[X, Y]|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

Now, if you test that, you might remark that the program loops just as yours when you hit the ; key. That's because Prolog thinks the second clause can apply to 0 too.

So let's edit the program once more:

s1(0, []).
s1(N, [[X, Y]|Q]) :-
    N > 0,
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

Now everything is fine.

I hope this'll help you to get a better understanding of how to build a proper predicate through recursion. I didn't spend much time correcting your addToEnd/3 predicate because my rambling about variables should already have told you a lot about what's wrong about it.