What is the downside of using difference lists in an append operation in Prolog?

Question

This is a follow-up question to this question about difference lists.

Generally, append/3 or conc/3 is written as follows:

append([], L, L).
append([H1|T1], L2, [H1|L3]):-
    append(T1, L2, L3).

The downside of this recursion is that it doesn't run efficiently when taking a long list as first argument because the whole list needs to be processed before the actual appending can begin.

To make this more efficient, we can use different lists which only requires variable instantiation and no recursion to append lists.

append_d(A1-Z1, Z1-Z2, A1-Z2).

The thing is that wherever I am looking for definitions of the append/3 predicate, the former is used, and not the supposedly more efficient alternative. Why is that? What is the downside of working with difference lists, and don't they justify the efficiency gain?

Answer 1

I guess the only "downside" of using a difference list version of append instead of the classical append/3 is that you maybe don't have a difference list to start with. In other words, if you have a list like this:

[a,b,c]

instead of this:

[a,b,c|Back]

... then you must traverse it if you want to append something to its end.

As long as you are going to append lists to each other, you will indeed use difference lists from the start. BTW, in modern Prolog separate arguments for the list and the rest are usually used. Here are a few SWI-Prolog library predicates that use difference lists:

• findall/4
• read_pending_codes/3
• phrase/3 (DCGs are discussed in the answer by @mat)

This list is definitely not exhaustive. The point is that these predicates, by using difference lists, allow you to add more to the back of the list in constant time.

As soon as you find yourself using append/3 for appending lists in a program you are writing, you should consider using difference lists instead. As for downsides, as long as you don't need to append lists, you need to carry around an extra argument that you don't use for anything: then, a just a list is good enough.

Furthermore, append/3, as it is usually implemented, can do many more things than just append lists. Try the following queries:

?- append(A, B, [1,2,3]). % split a list
?- append([1,2,3], Back, List). % make a difference list
?- append(Prefix, _, [a,b,c,d]). % list prefix
?- append(_, Suffix, [a,b,c,d]). % list suffix

and so on.

One nice example of a good use of difference lists are Prolog queues (see at the bottom of this answer, example is stolen, in simplified form, from "The Craft of Prolog" by Richard O'Keefe).

Afterword

While you might define a "difference list append" predicate, usually it is unnecessary, as it only adds a level of indirection. Say I'm writing a predicate that takes a binary tree and gives you the difference list (list and its back) resulting from in-order traversal:

% tree_inorder_list(+Tree, -List, -Back)
tree_inorder_list(nil, List, List).
tree_inorder_list(t(X, L, R), List, Back) :-
    tree_inorder_list(L, List, [X|List0]),
    tree_inorder_list(R, List0, Back).

Using a separate predicate for appending would only add code.

And yes, this could be written as a DCG instead! It looks much better:

tree_inorder(nil) --> [].
tree_inorder(t(X, L, R)) -->
    tree_inorder(L),
    [X],
    tree_inorder(R).

Instead of querying:

?- tree_inorder_list(Tree, List, []).

you would have to query, for the DCG version:

?- phrase(tree_inorder(T), List).

You can use listing/1 to see how this DCG definition translates to a Prolog predicate:

?- listing(tree_inorder//1).
tree_inorder(nil, A, A).
tree_inorder(t(D, A, E), B, G) :-
    tree_inorder(A, B, C),
    C=[D|F],
    tree_inorder(E, F, G).

true.

This is identical to the difference list definition above (except for one unification, C=[D|F], which is not inlined).

And because there is a difference-list phrase/3, you can use tree_inorder//1 on more than one tree in the difference list mode, and concatenate the lists in constant time:

?- list_to_search_tree([c,a,b], A),
   phrase(tree_inorder(A), List, Back),
   list_to_search_tree([z,y,z,z,x], B),
   phrase(tree_inorder(B), Back).
A = t(b, t(a, nil, nil), t(c, nil, nil)),
B = t(y, t(x, nil, nil), t(z, nil, nil)),
List = [a, b, c, x, y, z],
Back = [x, y, z].

(Thank you to @WillNess for suggesting this addition)

Answer 2

I would actually reformulate this question as:

What is the downside of using append/3 over other methods?

Answer: Frequent use of append/3 typically indicates a problem with your datastructures, and in such situations you should take a step back and consider using DCGs instead.

The fact that repeated use of append/3 typically means quadratic overhead in situations where using a DCG improves this to linear time (totalling over all operations) alone already often justifies this.

In addition, using a DCG often makes your code easier to read, since you need to keep track of fewer arguments and fewer variables.

Since you have now posted several related questions about list differences, my recommendation for you is to forget about them for now. In my opinion, the material you are using for learning Prolog may put too little emphasis on DCGs, so that you are running into the much harder topic of list differences too soon.

When tempted to use append/3, always consider using DCGs for describing lists instead! In my view, the fact that they are internally compiled to predicates that reason over list differences need not concern you for now. You will understand list differences much more easily later!

Note that when using DCGs, there is no need at all for append/3, since a concatenation of lists that are both described by nonterminals is much more naturally written for example as:

?- phrase((a,b), Ls).

where a and b are both nonterminals. Note how (',')//2 can be read as "and then" in DCGs, completely eliminating the need for append/3, and also eliminating the need to understand list differences so soon.

EDIT: I would like to back up my arguments with a quote from the publication Teaching Beginners Prolog — How to teach Prolog:

The second mistake is to introduce differences too early in a course. It is tempting to present list differences first and only then definite clause grammars, but beginners are much more comfortable with grammar rules.

This is definitely not an empirical study as requested in the comments. Still, I think the published experience of a Prolog teacher who has taught Prolog to students at universites in at least 3 different countries over several decades should be taken into account to some extent, even if we ignore the fact that we have a concrete beginner at hand who has already filed 3 different questions about list differences in the last 2 days.