Differential lists
| Guide to Prolog Programming |
© Roman Barták, 1998 |
| Home Prolog in Examples Prolog Data Structures |
|
List Processing
|
|
List is a data structure directly supported in Prolog via operations for accessing head and tail of the list. However, list is still a traditional Prolog term, if one uses the obvious dot notation. We described manipulation with lists in the section "Representing Data Structures" so we just look at differential lists here and we proceed to chapters presenting areas of using lists.
Differential listsThe main problem of Prolog implementation of lists is their one-way nature. It means that if one wants to access the n-th element, he/she has also to access all the previous elements in the list. In particular, if one wants to add an element to the end of the list, it is necessary to go through all elements in the list as the following programm shows (compare it with the implementation of append):
add2end(X,[H|T],[H|NewT]):-add2end(X,T,NewT). add2end(X,[],[X]).
But there is a technique, called differential lists, that enable appending lists or adding element to the end of list in one step. Nevertheless, it should be noted that this technique does not remove the disadvantage of visiting all previous elements in the list if the n-th element is accessed.
A differential list consist of two parts A-B and represents the list that is obtained from A by removing the tail B, e.g., [1,2,3,4]-[3,4] represents the list [1,2]. Ofcourse, if both lists A and B are ground, than there is no advantage of using differential lists, but if this technique is combined with the advantages of free variables and unification we can get impressive results. Namely, the list [1,2] can be represented by the differential list [1,2|X]-X.
If we standardize differential lists in the later way, we can write "one-step" procedures for appending lists and adding element to the end of the list:
append(A-B,B-D,A-D). add2end(X,A-B,A-NewB):-B=[X|NewB].
Note, that the other list operations, e.g., member, have also to be rewritten to work with differential lists.
as well as a generalized list processor.
|
|
|
| Designed and maintained by Roman Barták | |