Search code examples
prologdcgdifference-lists

Structure (Difference Lists) Prolog

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

Solution

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