In logic programming, the programmation with incomplete
structures is a well-known technique.
It is even a part where the logic
programming paradigm is at its best.
One example of this technique
is the difference-list (noted List-SubList).
A list is represented by the difference between
a Prolog list and one of its sublists (the tail of the list)
that must be an unknown.
For instance, the empty list is represented by
X-X and cons(1,cons(2,cons(3,nil))) is represented by
[1,2,3|X]-X.
Because the tail is an unknown, two lists can be concatenated with only one unification which is a binding of the tail. Then, a list can be a left concatenand only once in its life.
dconc(A-ZA, ZA-ZB, A-ZB). dconc3(A-ZA, ZA-ZB, ZB-ZC, A-ZC).
Note that, unlike predicate conc, dconc cannot be used to
split a list. Nothing in Prolog enforces the constraint that the tail
is a sublist of the list. So Prolog will bind ZA to something which is
neither a sublist of A nor a superlist of ZB.
Verifying the constraint can only result from a programming discipline.
Another difficulty is that testing the empty list requires to
perform an occurrence-check because otherwise
Prolog is always willing to unify [...|Z]-Z and
X-X.
Similarly, lack of occurrence-check makes an attempt to concatenate a
difference-list to itself succeed and produce an infinite term.
For all these reasons, the following predicates are bogus.
dtwice(L, LL) :- dconc(L, L, LL). common_prefix(P, L1, L2) :- dconc(P, _, L1), dconc(P, _, L2).
However, transformation of the representation of lists,
followed by some partial evaluation[SS86],
generally leads to more efficient programs.
nrev can be transformed into the following predicates:
revd1([], Y, Y). revd1([A|L], Y, Z) :- revd1(L, [A|Y], Z). revd(L, RL) :- revd1(L, [], RL).
Transforming difference-lists into Prolog lists is trivial
(if it is allowed to be destructive as dconc is), but
the way back needs to use predicate conc.
dlist2list(L-nil, L). list2dlist(L, AL-ZL) :- conc(L, ZL, AL).