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).` `…

Accepted Answer

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.

Prolog - recursive list building

Solution

Problem