How do you append an element to a list in place in Prolog?

Question

If I have a list in Prolog such as X = [1, 2, 3, 4], how do I add the element 5 to the end of the list to have X = [1, 2, 3, 4, 5]?

The append function needs two lists, ie append(A,B,C) to get A and B concatenated to the list C.

I can do this with a temporary list Y = [1, 2, 3, 4] and Z = [5], to then do an append(Y, Z, X), but I don't like having a temporary list.

The usual disclaimers apply here - this is not homework and I am just learning Prolog.

Gregarious

Short answer: You don't; you simply don't. – Varicotomy

Answer 1

Variables in Prolog can only be assigned once. As soon as X has the value [1,2,3,4] it can never have another value. A temporary variable and append/3, like you mentioned, is the way to do it.

Having said that, you can do one trick which probably isn't recommended. If X = [1,2,3,4,Y] then you can do Y=5 and X now has the value you want. I believe this technique is called a difference list.

Anuria

@no-one-in-particular Think about Prolog variables as mathematical variables instead of storage locations. I'm aware it is a major paradigm shift, but when you got it, anything in Prolog will be quite easy (or logical at least). – Lands

@Anuria - nice answer. This clears thinks up. So if I understand correctly, if I say X=[A,B,C,D] and then later assign A=[1], B=[2], then X=[[1], [2], C, D]. Then later, if I assign C=[3], D=[4], then I finally have X=[[1],[2],[3],[4]] and it is fixed in stone. – Gregarious

In order to use a difference list, you need to keep track of the "hole" in the list (in this case, its tail). I.e a difference list is always a pair of two terms, one being a list with the "hole" and the other being the "hole" itself. The "hole" itself is a logical variable. The traditional way of representing the pair is to use a built-in infix operator. – Steam

not exactly. with X = [1,2,3,4 | Y] and then Y = [5 | Z] this is the difference-list technique: appending 5 at the end of X...Y gets us the lengthened X...Z. the former X...Y is a still valid, shorter difference list, still representing the same prefix 1,2,3,4 as it did before the extension. difference-list are easy to understand as open-ended lists, or prefixes. Also, extending a difference list in this way is an O(1) oepration. – Erland

the "not exactly" was in response to "I believe this technique is called a difference list." in the answer. – Erland

Answer 2

As the others have pointed out, you're going to be stuck with the performance issue.
But just as an exercise I decided to try and create a predicate that could append an element to the end of a list, without using append.

% add_tail(+List,+Element,-List)
% Add the given element to the end of the list, without using the "append" predicate.
add_tail([],X,[X]).
add_tail([H|T],X,[H|L]):-add_tail(T,X,L).

I would advice that you'd simply use the append function, as a built-in function it is likely to be faster than anything manually crafted.

Fernand

In the style of Benjamin Franklin: "Those who would give up essential correctness to purchase a little temporary performance, deserve neither correctness nor performance." – Varicotomy

What's the difference then between add_tail(X,[L1],[L2]) and add_tail(X,[Y|L1],[Z|L2]) ? – Inspissate

[Head1, Head2|Tail] would remove the first 2 variables from the front of the list and put the remainder in a separate list in the variable Tail. So [1,2,3,4] would mean Head1 = [1], Head2 = [2], Tail = [3,4], meaning through recursion you can remove the front elements of a list. The add_tail reads as follows 1. If the first list is empty and X is now the last element of the outputList, stop searching for alternatives. 2. Take the first variable from the inputList, pass on X for the check, recursively unify H to the front of outputList when 1. is true. 1. ensures backstepping. – Sentimentality

Basically, remove all elements from List1, add X to an empty list and then add all elements from List1 in reverse order of removal back to List2, creating [List1|X] which you normally can't do because X would be checked against the existing Tail and fail. – Sentimentality

Answer 3

One declarative solution is to use a difference list (as Daniel suggested in its answer). A difference list gets its name from being usually represented as a difference between two lists: a list and its tail. For example, an empty list can be represented as T-T. A list with the elements 1, 2, and 3 can be represented as [1,2,3| T]-T (note that (-)/2 is standard built-in infix operator). The advantage of this representation is that you can append an element to a list in constant time by using a single fact definition of the append/3 predicate:

append(L1-T1, T1-T2, L1-T2).

An usage example:

?- append([1,2,3,4| T1]-T1, [5| T2]-T2, Result).
T1 = [5|T2],
Result = [1, 2, 3, 4, 5|T2]-T2.

If necessary, is not difficult to convert between a "normal" list and a difference list. I leave that as an exercise to you.

Steam

Just noticed this is a very old question (in Internet time)! – Steam

s(X): solid as a rock. – Varicotomy

Answer 4

You can't modify lists in Prolog, but you can create a list with an unspecified length:

main :-
    A = [1,2,3,4|_].

Then, you can insert an element using nth0/3 in SWI-Prolog:

:- initialization(main).

main :-
    A = [1,2,3,4|_],
    nth0(4,A,5),
    writeln(A).

After this element is inserted, A = [1,2,3,4,5|_].

You can also define a function that appends an item to the end of a list in-place, and then use it like this:

:- initialization(main).

append_to_list(List,Item) :-
    List = [Start|[To_add|Rest]],
    nonvar(Start),
    (var(To_add),To_add=Item;append_to_list([To_add|Rest],Item)).

main :-
    A = [1,2,3|_],
    append_to_list(A,4),
    append_to_list(A,4),
    writeln(A).

In this example, A = [1,2,3,4,4|_] after these two items are appended.

Benzyl

you could also add that retracing the open list from its start anew on each appending will be quadratic overall, so we could maintain the end var explicitly for the O(1) appending - and it would be the difference list then. also, another approach is to maintain the known length and use nth0/nth1 directly. – Erland

Answer 5

Since Prolog has append which only accepts lists, why don't we use it to insert our element in one of the lists. i.e.

% E = element, L = list, R = result
% e.g. add_elem_in_list ([1,2,3,4], 5, R).
add_elem_in_list(L, E, R) :- append(L, [E], R).

Ul

Answer 6

You're worrying about the wrong end of the problem. Structure sharing can only happen by consing an element onto the beginning of the list. That method has the performance characteristics you want. Because of the way lists are defined, when you append two lists the entire first list will be copied. In this case, that's going to be the whole list. The garbage generated by a one-item list is obviously going to be much smaller than that.

If you really must append, consider building the list backwards and then reversing it once at the end, which is much cheaper, or use difference lists, which enable efficient appending to the end.

Clancy

s(X) for the classic "double reversal, prepend item" approach! – Varicotomy