Prolog - Recursive append to list returning false

Question

Title says it all, but here we are again. Trying to append recursively to a list in Prolog, and while I have previously gotten it to work by having "temporary buffers" (via nb_setval/nb_getval) I'd like to learn how to, in a slightly more appropriate way, recursively append to lists.

I've understood Prolog works all around bindings and once something is bound it's difficult to manipulate it, so initially I sat with this, but I've understood why that does not quite work:

recursiveAppend([], _).
recursiveAppend([H|T], Output):-
    append(H, [], Output),
    recursiveAppend(T, Output).

That made me change the code and go to the following:

recursiveAppend([], _).
recursiveAppend([H|T], Output):-
    append(H, Output, NewOutput),
    recursiveAppend(T, NewOutput).

Which I had hoped would work, as it made sense to myself and apparently to others while scouring other StackOverflow questions as well. Unfortunately, calling this predicate in SWI-Prolog only returns false.

?- recursiveAppend([1, 2, 3, 4, 5], L1). false

Expected/desired result would, in this case, be:

?- recursiveAppend([1, 2, 3, 4, 5], L1). L1 = [1, 2, 3, 4, 5].

For the sake of clarification, the runtime of the program should look something like this if "fleshed out":

recursiveAppend([H|T], Output):-
    % H is 1, Output is []
    append(H, Output, NewOutput),
    % NewOutput is [1]
    recursiveAppend(T, NewOutput).

recursiveAppend([H|T], Output):-
    % H is 2, Output is [1]
    append(H, Output, NewOutput),
    % NewOutput is [1, 2]
    recursiveAppend(T, NewOutput).

recursiveAppend([H|T], Output):-
    % H is 3, Output is [1, 2]
    append(H, Output, NewOutput),
    % NewOutput is [1, 2, 3]
    recursiveAppend(T, NewOutput).

recursiveAppend([H|T], Output):-
    % H is 4, Output is [1, 2, 3]
    append(H, Output, NewOutput),
    % NewOutput is [1, 2, 3, 4]
    recursiveAppend(T, NewOutput).

recursiveAppend([H|T], Output):-
    % H is 5, Output is [1, 2, 3, 4]
    append(H, Output, NewOutput),
    % NewOutput is [1, 2, 3, 4, 5]
    recursiveAppend(T, NewOutput).

recursiveAppend([], _). % First argument (list) is empty, and the second argument (list) has been populated (with [1, 2, 3, 4, 5]), program done.

Any and all help is appreciated, even though this question has probably been asked a million times before!

what is it appending? it's unclear. the example does not clarify: recursiveAppend([1, 2, 3, 4, 5], L1), L1 = [1, 2, 3, 4, 5]. can be simply coded as recursiveAppend(A, L1) :- L1 = A.. give more examples which can't be misinterpreted and show your intentions clearer please. — Will Ness
@WillNess Have expanded the question now, hopefully something that should be able to help you understand what I'm trying to achieve? — Xariez
no, you haven't shown us "more examples" of input-output pairings which I asked for. "input" means "here's a test call I try at the REPL", "output" means "here's what I want to see it respond". you seem to not understand basic Prolog. start with tutorials from the very start. ask questions about each smallest possible thing you don't understand, don't be building castles on quicksand foundations and then ask us why this large structure isn't standing right, or at all. when you learn, verify every new step in your growing understanding by writing small programs and trying them at the REPL. — Will Ness

Isabelle Newbie Isabelle Newbie · Accepted Answer · 2020-09-28T08:50:49

"Recursive append" is not something that often makes sense in Prolog. The question should include information about what problem you are trying to solve. Currently it is not about that; it is about how you are trying to solve your problem. That "how" is "recursive append", but this is almost certainly not how you should really solve that problem. We could offer better help if we knew what the problem was, not how you think you want to solve it.

Taking the example from the question and the solution from https://stackoverflow.com/a/64092447/4391743:

?- recursiveAppend([1, 2, 3], Ys).
Ys = [1, 2, 3].

?- recursiveAppend(Xs, [1, 2, 3]).
Xs = [1, 2, 3] ;
% nontermination after first answer

?- recursiveAppend([1, 2, X], [A, B, 3]).
X = 3,
A = 1,
B = 2.

?- recursiveAppend([1, 2 | Rest], [A, B, 3, 4]).
Rest = [3, 4],
A = 1,
B = 2 ;
% nontermination after first answer

If this is what you want, then what you seem to want is a "list copy" predicate. Here's a shorter, faster, more complete one:

list_copy([], []).
list_copy([X | Xs], [X | Ys]) :-
    list_copy(Xs, Ys).

This doesn't have the non-termination issues that the above predicate has:

?- list_copy([1, 2, 3], Ys).
Ys = [1, 2, 3].

?- list_copy(Xs, [1, 2, 3]).
Xs = [1, 2, 3].

?- list_copy([1, 2, X], [A, B, 3]).
X = 3,
A = 1,
B = 2.

?- list_copy([1, 2 | Rest], [A, B, 3, 4]).
Rest = [3, 4],
A = 1,
B = 2.

If one of the arguments is a list and the other is a variable, a new list structure will be built up and bound to this variable.

But... why do you need a new list structure at all? In pure Prolog you can't tell whether two terms are the same (i.e., sharing the same memory location) or "just" structurally equal. Neither do (or should) you usually care. (There are uses for knowledge about sharing, and about explicit copying, in non-pure Prolog, but again we don't know what you're trying to do.)

So if we can't tell whether a "copy" is indeed a copy or just "an equal term", then we don't need to copy at all. We can get the exact same behavior as above with just unification:

?- [1, 2, 3] = Ys.
Ys = [1, 2, 3].

?- Xs = [1, 2, 3].
Xs = [1, 2, 3].

?- [1, 2, X] = [A, B, 3].
X = 3,
A = 1,
B = 2.

?- [1, 2 | Rest] = [A, B, 3, 4].
Rest = [3, 4],
A = 1,
B = 2.

No copying and certainly no "recursive append" is needed to achieve unification, Prolog knows how to do unification for you.

If this is not what you want, please tell us what the actual problem is. "Recursive append" is almost certainly not it.

Prolog - Recursive append to list returning false

2 Answers