Difference between "open-ended lists" and "difference lists"

Question

What is the difference between "open-ended lists" and "difference lists"?

Answer 1

As explained on http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html, open list is a tool used to implement a difference list.

Open list is any list where you have a unassigned variable at some point in the list, e.g.: [a,b,c|X]. You can use open list to implement a data structure called difference list, which formally specifies a structure of two terms pointing to first element and to the open end, traditionally defined as: [a,b,c|X]-X, to make operating on such lists easier.

For example, if all you have is an open list, adding element to the end is possible, but you need to iterate over all items. In a difference list you can just use the end-of-list variable (called a Hole on the page above) to skip iteration and perform the operation in constant time.

Answer 2

Both notions seem to be lists, but in fact they are not. One is a concrete term, the other rather a convention.

Open-ended lists, partial lists

Open-ended lists are terms that are not lists but can be instantiated such that they become lists. In standard lingo, they are called partial lists. Here are partial lists: X, [a|X], [X|X] are all partial lists.

The notion open-ended lists suggests a certain usage of such lists to simulate some open-ended state. Think of a dictionary that might be represented by an open-ended list. Every time you add a new item, the variable "at the end of the partial list" is instantiated to a new element. While this programming technique is quite possible in Prolog, it has one big downside: The programs will heavily depend on a procedural interpretation. And in many situations there is no way to have a declarative interpretation at all.

Difference lists

Difference lists are effectively not lists as such but a certain way how lists are used such that the intended list is represented by two variables: one for the start and one for the end of the list. For this reason it would help a lot to rather talk of list differences instead of difference lists.

Consider:

el(E, [E|L],L).

Here, the last two arguments can be seen as forming a difference: a list that contains the single element [E]. You can now construct more complex lists out of simpler ones, provided you respect certain conventions which are essentially that the second argument is only passed further on. The differences as such are never compared to each other!

el2(E, F, L0,L) :-
   el(E, L0,L1),
   el(F, L1,L).

Note that this is merely a convention. The lists are not enforced. Think of:

?- el2(E, F, L, nonlist).
   L = [E,F|nonlist].

This technique is also used to encode dcgs.

Answer 3

For example

Open-ended : [a,b,c | _]

Difference-list : [a,b,c|U]-U.