Prolog - Recursively append numbers to a list

Question

I am just starting to learn Prolog, and I am having troubles wrapping my head around recursive concepts. Right now, solely for the purpose of practice, I am trying to write a program that appends 10 numbers to a list and then prints out that list.

The self-imposed rule for this program is that the list has to be 'declared' (I am not sure if that is the correct word for Prolog) in a main predicate, which calls another predicate to append numbers to the list.

This is what I have so far, and I know it won't work because I am trying to redefine List at the end of the addToList predicate, which is not allowed in the language.

% Entry point that declares a list (`List`) to store the 10 numbers
printList(List) :-
    addToList(0, List),
    writeln(List).

% Base case - once we hit 11 we can stop adding numbers to the list
addToList(11, _).

% First case - this predicate makes adding the first number easier for me...
addToList(0, List) :-
    append([], [0], NewList),
    addToList(1, NewList),
    append([],  NewList, List). % This is valid, but List will just be [0] I think..

% Cases 1-10
addToList(Value, List) :-
    append(List, [Value], NewList),
    NextVal is Value+1,
    addToList(NextVal, NewList),
    append([], NewList, List). % This is INVALID since List is already defined

This program would be started with:

printList(List).

Is there a simple way to change up the broken program I have written up to make it work correctly? I am super lost on how to get the numbers stored in List.

rajashekar rajashekar · Accepted Answer · 2020-11-14T05:48:28

You are thinking procedurally, in prolog you cannot change variables. You are trying to construct the list yourself. In prolog-style you try to declare the constraints of the list you want. If nlist/2 is a predicate that gives a list of N numbers then what exactly are it's properties? nlist(0, []). and if nlist(N, Xs) then nlist(N+1, [N+1 | Xs]). So you just write these and let prolog take care of the construction.

nlist(0, []).
nlist(N, [N | Xs]) :-
    N>0, N1 is N-1,
    nlist(N1, Xs).

If you are confused how the recursion calls are taking place, try using trace/0 or trace/1. You can see how the calls are being done in the following trace. You can get this by calling trace(nlist).

?- nlist(3, X).
 T Call: nlist(3, _78)
 T Call: nlist(2, _902)
 T Call: nlist(1, _1464)
 T Call: nlist(0, _2026)
 T Exit: nlist(0, [])
 T Exit: nlist(1, [1])
 T Exit: nlist(2, [2, 1])
 T Exit: nlist(3, [3, 2, 1])
X = [3, 2, 1]

A more procedural style code will be as follows

addToList(11, A, A).

% Cases 1-10
addToList(Value, List, NewList) :-
    Value < 11,  append(List, [Value], Temp),
    NextVal is Value+1,
    addToList(NextVal, Temp, NewList).

This gives the middle parameter is the accumulator. When you reach 11 the accumulator is the answer.

?- addToList(1, [], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 

?- addToList(5, [], X).
X = [5, 6, 7, 8, 9, 10]

Look at the sample trace and the difference between them in nlist and addToList. Try to figure out the differences and why the are happening.

?- addToList(7, [], X).
 T Call: addToList(7, [], _33565254)
 T Call: addToList(8, [7], _33565254)
 T Call: addToList(9, [7, 8], _33565254)
 T Call: addToList(10, [7, 8, 9], _33565254)
 T Call: addToList(11, [7, 8, 9, 10], _33565254)
 T Exit: addToList(11, [7, 8, 9, 10], [7, 8, 9, 10])
 T Exit: addToList(10, [7, 8, 9], [7, 8, 9, 10])
 T Exit: addToList(9, [7, 8], [7, 8, 9, 10])
 T Exit: addToList(8, [7], [7, 8, 9, 10])
 T Exit: addToList(7, [], [7, 8, 9, 10])
X = [7, 8, 9, 10]

Prolog - Recursively append numbers to a list

2 Answers