Prolog Tutorial 7: Lists as Accumulators

James Power, 1997.


In the previous tutorial we have concentrated on moving through lists and processing their elements in the usual head/tail fashion. In this section we want to look at predicates that build new lists.


Collecting information

Suppose we wanted to write a predicate that took a single argument, and printed out all the numbers between it and 0. We might write: If we try running this we would get something like: Now suppose we wanted to take these numbers and process them in some other part of the program; to do this we would have to store them somewhere - the natural choice is to use a list. Thus we'd want a predicate of the form collect_to(N,L) where N was the input number, and L was the list containing the answer.

This will be slightly different to the other list predicates, since now we want to build a list as we iterate, rather than take one apart. However, the process will still use the standard "[H|T]" notation that we have been using.

We should work it out int he usual recursive manner:

The above solution is correct, but as you get used to lists in Prolog you'll find ways to take advantage of its pattern-matching; the more common way of writing this predicate would be:
  new_collect_to(0,[]).
  new_collect_to(N,[N|T]) :- N>0, N1 is N-1, new_collect_to(N1,T).
You should try both of these to make sure that they work, and that they both do the same thing! If the second, more compact version doesn't seem so natural, then you can stick to the first (longer) method of defining this kind of predicate for the moment.


Joining two lists

We can write a predicate to join two lists together; the predicate join_list(L1,L2,L3) means "if we join L1 and L2 we get L3".

If we consider the possibilities for L1

  1. L1 is the empty list, in which case L3 is just L2
  2. L1 is of the form [H1 | T1].
    If we are to append L2 on to the end of this we will get a list whose head is still H1, but whose tail is the result of appending T1 and L2

Thus an initial attempt might be:

  join_list(L1,L2,L3) :- L1=[], L3=L2.
  join_list(L1,L2,L3) :- L1=[H1|T1], join_list(T1,L2,T3), L3=[H1|T3].
Since we know that Prolog will do unification when it matches parameters against arguments, a simpler (but equivalent) solution would be:
  join_list([], L2, L2).
  join_list([H1|T1], L2, [H1|L3]) :-  join_list(T1,L2,L3).

Type in the join_list predicate, and try the following queries:

Prolog has a built-in version of this predicate called append/3.


Reversing a List

Another good example of accumulating results in a list is a predicate to reverse a list. Presumably the predicate will be of the form reverse(L1,L2), where L2 is just L1 backward.

One rather bad way of doing this would be:

  % bad_reverse(L1,L2) -  a bad implementation of list reversal
  bad_reverse([],[]).
  bad_reverse([H|T], L2) :-
    bad_reverse(T,NT), append(NT,[H],L2).
The problem with this is that it works rather inefficiently - the second predicate goes through the tail once to reverse it (putting the result into NT), and then again in order to stick H onto the end.

If we think about the problem for a while, we can see that we need to go through L1, and put each element that we met into L2; for example, reversing the list [1,2,3] should go something like:

	Input		Output
	-----		------

	[1,2,3]		[ ]
	[2,3]		[1]
	[3]		[2,1]
	[ ]		[3,2,1]
Unfortunately, there's no real way of doing this with just two lists. What we need to do is to mimic the "Towers of Hanoi" example a little, and use an intermediate list to store the answer that we're creating. When we're done, we can just copy this to the output list.

In the Prolog library, there's an implementation of this as follows:

%   myreverse(?List, ?Reversed)
%   is true when Reversed is has the same element as List but in a reversed 
%   order. List must be a proper list.

good_reverse(List, Reversed) :-
	good_reverse(List, [], Reversed).

good_reverse([], Reversed, Reversed).
good_reverse([Head|Tail], SoFar, Reversed) :-
	good_reverse(Tail, [Head|SoFar], Reversed).

I've called this good_reverse/2 to stop it clashing with the built-in reverse/2 predicate.

The last two predicates above actually have three arguments (the input list, an intermediate list, and the output list), and so are different from the first one (which only has two). What happens here is that the user calls the first predicate, and this then calls the three-argument version with the empty list as the starting point for the intermediate storage. good_reverse/3 then copies the first list into the intermediate until it's empty, and then copies the intermediate list to the output list.

Make sure that you understand this example - try running the following version (which prints out what it's doing) with some queries...

%   pr_reverse(?List, ?Reversed)
%   is true when Reversed is has the same element as List but in a reversed 
%   order. List must be a proper list.

pr_reverse(List, Reversed) :-
	pr_reverse(List, [], Reversed).

pr_reverse([], Reversed, Reversed) :-
        format("\nInput=~q, Intermediate=~q, Output=~q",[[],Reversed,Reversed]).
pr_reverse([Head|Tail], SoFar, Reversed) :-
        format("\nInput=~q, Intermediate=~q, Output=~q",[[Head|Tail],SoFar,Reversed]),
	pr_reverse(Tail, [Head|SoFar], Reversed).

Here, format/2 is a built-in printing predicate that works a little like printf in C or Java. It's described in section 7.14 of the GNU Prolog manual.


Exercises

  1. Write predicates for the following:
    1. cutlast(L1,L2) which is true if L2 is L1 with the last element removed
    2. trim(L1,N,L2) which is true if L2 contains just the first N elements of L1
    3. evens(L1,L2) which is true if L2 contains just those elements in L1 which are even in the same order
  2. Write a predicate beg_small(L1,L2) which is true if L2 has the smallest number in L1 as its head, and all the other numbers in the same order
  3. Use recursion and the last predicate to implement a predicate that sorts a list by iteratively moving the smallest element to the head, then the next smallest to the second position and so on.
  4. Write a predicate split(L1,N,L2,L3) which is true if L2 contains those elements of L1 less than or equal to N, and L3 contains those elements of L1 greater than N. (This is a lot like the ordered binary trees example.)
  5. Use the last predicate to implement a quicksort as follows:
    1. Sorting the empty list gives you the empty list
    2. To sort a list of the form [H|T], call split(T,H,T1,T2), sort T1 and T2, and then append these along with H (in the middle) together to form the answer.

Built-In list predicates

Many of the predicates that you will most commonly use when working with lists (such as those in the previous section) are built-in to Prolog. Some of the more common ones are listed in section 7.20 of the GNU Prolog manual.

You might notice the format of the definitions; for example length(?list, ?integer). This not only gives a hint as to the expected type of the arguments to the predicate, but also to their "mode". The notation is pretty standard:


Written by James Power
Released under the GNU Free Documentation License
Last revised: 22 Oct 2006

+Argthe argument must be instantiated.
-Arg the argument must be a variable (will be instantiated if the built-in predicate succeeds).
?Argthe argument can be instantiated or a variable