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.

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

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

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

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

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

View more solutions