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

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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.