Logical variables can occur anywhere, not only as arguments of clause heads and goals, but also within data structures. A data structure which contains variables is called a partial data structure, because it will eventually be completed by substituting the variable with an actual data term. The most common case of a partial data structure is a list whose tail is not yet instantiated.
Consider first an example where no partial lists occur. In the following query, a list is built incrementally, starting from its end:
?- L1 = [], L2 = [c|L1], L3 = [b|L2], L4 = [a|L3]. L1 = [] L2 = [c] L3 = [b, c] L4 = [a, b, c]
Whenever a new head/tail cell is created, the tail is already instantiated to a complete list.
But it is also possible to build the list from the front. The following code, in which the goals have been reordered, gives the same final result as the code above:
?- L4 = [a|L3], L3 = [b|L2], L2 = [c|L1], L1 = []. L1 = [] L2 = [c] L3 = [b, c] L4 = [a, b, c]
However, in the course of the computation, variables get instantiated to ”partial lists”, i.e. lists whose head is known, but whose tail is not. This is perfectly legal: due to the nature of the logical variable, the tail can be filled in later by instantiating the variable.