How do I append 3 lists efficiently in Prolog?

Question

I know how to do it for 2 lists:

append([],L,L).
append([H|T],L,[H|R]):-append(T,L,R).

but how to do it for 3? Without using the append for 2 lists twice.

Answer 1

To append lists efficiently, consider using difference lists. A difference list is a list expressed using a term with two lists. The most common representation uses (-)/2 as the functor for the term. For example, the list [1,2,3] can be expressed as:

[1,2,3| Tail]-Tail.

By keeping track of the list tail, i.e. of its open end, you can do several operations efficiently. For example, you can append an element to end of the list in O(1) by instantiating the tail:

add_to_end_of_list(List-Tail, Element, List-Tail2) :-
    Tail = [Element| Tail2].

Or simply:

add_to_end_of_list(List-[Element| Tail2], Element, List-Tail2).

Let's try it:

?- add_to_end_of_list([1,2,3| Tail]-Tail, 4, Result).
Tail = [4|_G1006],
Result = [1, 2, 3, 4|_G1006]-_G1006.

Now, appending two lists is similar and also O(1). Instead of appending an element, we want to append a list of elements:

dappend(List1-Tail1, Tail1-Tail2, List1-Tail2).

For example:

?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result).
Tail1 = [4, 5, 6|Tail2],
Result = [1, 2, 3, 4, 5, 6|Tail2]-Tail2.

I leave to you as an exercise to answer your own question using difference lists. Note that going from a difference list to a closed list, is simply a question of instantiating the open end to the empty list. For example:

?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result-[]).
Tail1 = [4, 5, 6],
Tail2 = [],
Result = [1, 2, 3, 4, 5, 6].

However, going from a closed list to a difference list does requires you to traverse the list, which is O(n):

as_difflist([], Back-Back).
as_difflist([Head| Tail], [Head| Tail2]-Back) :-
    as_difflist(Tail, Tail2-Back).

The cost of constructing the difference lists may or may not be an issue, of course, depending on how you get the initial lists and how often you will be appending lists in your application.