Prolog Language Difference Lists Basic usage
Example
Let's consider the predicate sumDif/2, verified if the structure of a list matches several constraints. The first term represents the list to analyze and the second term another list that holds the part of the first list that is unknown to our constraints.
For the demonstration, sumDif/2 recognizes an arithmetic expression to sum n integers.
sumDif([X, +|OpenList], Hole) :-
integer(X),
sumDif(OpenList, Hole).
We know the first element of the list to validate is an integer, here illustrated by X, followed by the symbol of the addition (+). The remaining of the list that still needs to be processed later on (OpenList) is left unvalidated at that level. Hole represents the part of the list we don't need to validate.
Let's give another definition of the predicate sumDif/2 to complete the validation of the arithmetic expression:
sumDif([X|Hole], Hole) :-
integer(X).
We expect an integer called X directly at the start the open list. Interestingly, the remaining of the list Hole is left unknown and that's the whole purpose of the Difference Lists: the structure of the list is known up to a point.
Finally, the missing piece comes when a list is evaluated:
?- sumDif([1,+,2,+,3], []).
true
This is when the predicate is used that the end of the list is mentioned, here [], indicates the list does not contain additional elements.
