Data Structures in General

In general, all data structures (queues, stacks, n-ary trees, etc.) can be implemented using the ideas presented. Moreover, as all data is dynamic (in fact, there is no such concept as ``static variable''), and the user does not need to worry about memory management, dangling pointers, and the like, more sophisticated data structures can be used. Once familiar with the language, the programmer is able to focus on using the best data for the application at hand. Garbage collection is also automatic, so no memory leaks are possible (and, if they happen, they are the language implementor's fault, and not the programmer's).

More refined data structures are possible, using the advantage of having free variables inside the data: this leaves the interesting possibility of incrementally adding more items to the structure, and can be seen as ``open pointers''. Probably using them is not often necessary in CLP, where the focus is more in constraint solving than in building intricate data structure and coding refined algorithms--the solver already contains such algorithms. Notwithstanding, we will give two examples of using open data structures for problems already seen.

Example 3.4   We have shown how to insert pieces of information in a sorted binary tree. This takes three arguments, the first for the element to insert, the second for the old tree, and the third for the tree after insertion. Empty trees appeared as the constant void. We can use only two arguments by having free variables in the leaves, instead of void: when a leaf is reached, the variable is just further instantiated.

insert_ordtree(Element, tree(Element, L, R)):- !.
insert_ordtree(Element, tree(This, L, R)):-
   precedes(Element, This),
   insert_ordtree(Element, L).
insert_ordtree(Element, tree(This, L, R)):-
   precedes(This, Element),
   insert_ordtree(Element, R).

There is a trick and something not yet known. The `!' sign is a control primitive, which in this case means that ``after trying this clause, do not try the others below: commit to the decision you have made, even if you fail in the program afterwards'', and is called a cut. The trick is that, as the tree is traversed down, going left or right, using the second and third clauses, there must be a point in which the first clause matches: either we have found the element we want to insert (and there is no need to insert it, then) or we have reached a leaf, which is a free variable, and then it is instantiated and matches the first clause. This variable is bound to a tree/3 structure, with fresh, unbound variables for the right and left sons. Here is an example of using it:

?- insert_ordtree(k, X), insert_ordtree(l, X), 
   insert_ordtree(a, X), insert_ordtree(f, X), 
   insert_ordtree(z, X). 

   X = tree(k,tree(a,_,tree(f,_,_)),tree(l,_,tree(z,_,_)))

$\blacksquare$

Example 3.5   One of the best uses of open data structures is called difference lists. A difference list is a list which is expressed as the difference between two lists. We will use the construction Prefix-Suffix to denote a difference list; with this in mind, [a,b,c,d,e,f]-[d,e,f] is representing the list [a,b,c]. The interesting case is when the Suffix is a free variable, and this free variable can be instantiated to make the list grow at the tail without the need of appending. In fact, this can be seen in most cases as an constant-time append which does not need to traverse the whole list. If we have the construction [a,b,c|X]-X, and we instantiate X to be [d,e], then the Prefix will be instantiated to [a,b,c,d,e] in constant time.

We will use difference lists to rewrite the pre_order/2 program without the need of append at the end:

pre_order(Tree, List):- pre_order_open(Tree, List-[]).
pre_order_open(void, List-List).
pre_order_open(tree(X, Left, Right), [X|PrefLeft]-FinalRest):-
   pre_order_open(Left, PrefLeft-Pref),
   pre_order_open(Right, Pref-FinalRest).

Some hints to understand this code:

• L-L is the difference between two identical lists: thus it represents the empty list, which is [] in the closed lists case.
• The suffix of the list in the first recursive call to pre_order_open/2 is handed down to the second recursive call, in order for it to be instantiated.
• We want the toplevel call to return a closed list (but we may choose not to do so, actually). For this, we specify that the result of calling pre_order_open/2 should have [] as suffix.

In real applications, and when this technique is fully understood, the prefix and suffix of the lists are usually passed as separate arguments. $\blacksquare$