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.
% print_to(N) - prints out all the numbers down from N to 0 print_to(0) :- write(0). print_to(N) :- N>0, write(N), nl, N1 is N-1, print_to(N1).If we try running this we would get something like:
| ?- print_to(5). 5 4 3 2 1 0Now 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:
collect_to(0,L) :- L=[].
collect_to(N,L) :- N>0, N1 is N-1, collect_to(N1,T), L=[N|T].
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.
If we consider the possibilities for L1
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.
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.
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:
+Arg | the argument must be instantiated. |
-Arg | the argument must be a variable (will be instantiated if the built-in predicate succeeds). |
?Arg | the argument can be instantiated or a variable |
Written by James Power