These Pages are maintained by
Dr Peter Hancox
Last updated October 1998
The three patterns of list processing have been presented. Now we will look again at some of the selected examples.
% 1 terminating condition
app([], List, List).
% 2 recursive
app([Hd|Tl1], List2, [Hd|Tl3]) :-
app(Tl1, List2, Tl3).
We could use this to find:
| ?- app([a,b,c], [1,2,3], List).
List=[a,b,c,1,2,3] ? ;
no
This is the use we would expect of such a procedure: we're asking "what does [a,b,c] and [1,2,3] make when appended?". We can ask an alternative question: what pairs of lists, when appended, make [a,b,c,1,2,3].
| ?- app(List1, List2, [a,b,c,1,2,3]).
List1 = []
List2 = [a,b,c,1,2,3] ? ;
List1 = [a]
List2 = [b,c,1,2,3] ? ;
List1 = [a,b]
List2 = [c,1,2,3] ? ;
List1 = [a,b,c]
List2 = [1,2,3] ? ;
List1 = [a,b,c,1]
List2 = [2,3] ? ;
List1 = [a,b,c,1,2]
List2 = [3] ? ;
List1 = [a,b,c,1,2,3]
List2 = [] ? ;
no
We can see that there are seven possible pairs that make up the original list.
One way of looking at what we have done is that we have used this procedure normally (ie we have found what the appending of two lists will give), and "back-to-front" (ie by finding the question for which know the answer). This way of using procedures in more than one way is one of logic programming's strengths. Given enough imagination the part of the programmer, it is possible to create some very elegant and simple solutions to problems. However, as will be seen later in the course, it is quite easy to get caught out by inadvertently finding infinite branches in the search tree: ie situations where Prolog will recurse forever without finding a solution.
% 1 terminating condition
delete_element(Elem, [Elem|Tail], Tail).
% 2 recursive
delete_element(Elem, [Head|Tail1], [Head|Tail2]) :-
delete_element(Elem, Tail1, Tail2).
We have seen that we can use this to find what a list is with a particular item deleted:
| ?- delete_element(b, [a,b,c], [a,c]).
yes
| ?- delete_element(c, [a,b,c], List).
List = [a,b] ? ;
no
We can also use this procedure to find what lists can be created by adding a single element to it:
| ?- delete_element(b, List, [a,c]).
List = [b,a,c] ? ;
List = [a,b,c] ? ;
List = [a,c,b] ? ;
no
We can also use it to find what pairs of an element and a list can be made from another list:
| ?- delete_element(Elem, [a,b,c], List).
Elem = a
List = [b,c] ? ;
Elem = b
List = [a,c] ? ;
Elem = c
List = [a,b] ? ;
no
In a previous section, we defined memb/3 as:
% 1 terminating condition
memb(Elem, [Elem|_], Cnt) :-
write(Cnt),
nl.
% 2 recursive
memb(Elem, [_|Tail], Cnt) :-
Cnt1 is Cnt + 1,
memb(Elem, Tail, Cnt1).
and described its use to find the position at which a given element occurred. It seems very similar to position/3, which we defined as:
% 1 terminating condition
position(1, Elem, [Elem|_]).
% 2 recursive
position(Cnt, Elem, [_|Tail]) :-
Cnt1 is Cnt - 1,
position(Cnt1, Elem, Tail).
However, if we use position/3 to perform the functionality of memb/3, or vice versa, we will soon have instantiation errors because the variable Cnt will be uninstantiated.
The patterns of list processing given so far don't provide a way around this problem. However, there is another pattern of list processing that side-steps the problem and also offers more opportunity to write more efficient recursive programs. Procedures in this pattern are generally called accumulators.
These Pages are maintained by
Dr Peter Hancox
Last updated October 1998