Structure (Difference Lists) Prolog

Question

This question refers to the material in chapter 3 of the book: Programming in Prolog, Clocksin and Mellish, Ed 5

In page 72 of this book, a program using difference list is displayed:

partsOf(X,P):- partsacc(X,P,Hole) , Hole=[].

partsacc(X,[X|Hole],Hole):-basicpart(X).
partsacc(X,P,Hole):- assembly(X,Subparts), partsacclist(Subparts, P, Hole).

partsacclist([],Hole,Hole).
partsacclist([P|T], Total, Hole):- partsacc(P,Total,Hole1), partsacclist(T,Hole1,Hole).

In many tutorials online, the following format of using the "-" is used, for example::

append([ A , B , C | R1 ] – R1 , [ D , E | R2 ] – R2 , R3)

My questions are:

1. What is the difference between these two representations (Using - and not using it)

2. In which situations it is best to use each of them?

Thanks

Ostracod

Answer 1

By all means: Do not use (-)/2 or (\)/2 or any other operator to represent "difference lists". The reason is that you will often have a predicate with one list argument and an internal predicate that uses a difference list. With both having the same arity and probably also the same name, things will get confusing. Even worse, it might work for "some cases". Also, that operator will incur some cost you can avoid with two separate arguments.

Try to stick to a clean naming convention. That is S0, S1 ... S. In this manner the arguments representing the difference list will be easily visible. To better underline that those arguments belong together, some people do not use a space after the separating comma, whereas they use it for other arguments. Thus:

p(L+R, S0,S) :-
   p(L, S0,S1),
   p(R, S1,S).

Further, the (-)/2 has another meaning in Prolog. It is used to represent a pair Key-Value, as in keysort/2.

Any Prolog book I know suggesting an operator for difference lists comes from the 1980s.

Morven

@Will: There are authentic answers, now! – Morven

Answer 2

My experience in Prolog is limited, but it seems that older texts tend to use either the - or another character (for example \) to denote the list and its tail. Newer Prolog code always uses two arguments (as in your first example). For example, all built-in and library predicates in SWI-Prolog consistently use two separate arguments.

In theory, there is no difference which style you prefer. I guess it doesn't hurt to be consistent about it in your own code.

In practice, the difference is that instead of a compound term holding two lists in one single argument you have two arguments, which should be a more efficient representation.

EDIT

Make sure to also read the answer by @false.

Match

Answer 3

I agree with what Boris said (+1) regarding the different representations. Moreover, this is in my opinion clearly a case where you should use DCGs instead of encoding list differences explicitly. Consider for example the following version of the code:

parts(X) --> { basicpart(X) }, [X].
parts(X) --> { assembly(X, Parts) }, assembly_(Parts).

assembly_([])     --> [].
assembly_([X|Xs]) --> parts(X), assembly_(Xs).

Usage, after defining assembly/2 and basicpart/1 exactly as in your example:

?- phrase(parts(X), Ls).

The DCG has a clear declarative and easy to read interpretation, and requires fewer arguments.

Millstone