How to Learn Prolog { day - 3 }

Bind Variables

In our last lab, we searched a list to check if a given element is a member of that list or not. In that case, our code was-

member(X,[X|R]).

member(X,[Y|R]) :- member(X,R).

This can be also written as-

member(X,[X|_]).

member(X,[_|R]) :- member(X,R).

where '_' (underscore) designates a "don't-care" variable, usually called anonymous variables. In general, such variables have names whose first character is the underscore. In effect, they match any Prolog term, but no variable binding results from the free match. Notice that this is consistent with the original intentions of the definition of 'member'. Not having to bind values to anonymous variables saves a little run-space and run-time.

List Construction

The last example showed how we could strip off the front items on a list and recursively search the rest. We can also use the same method to build lists. For example take one existing list, say List1. We can make a new list List2 which contains List1 but with the new head prolog, as follows:

List2 = [prolog|List1]

This again is pure unification. List2 now consists of the head prolog plus whatever List1 was bound to. If List1 were to be bound e.g. List1 = [list,c,pascal,basic], List2 would now be the list [prolog,lisp,c,pascal,basic]

We can use this construction technique to build lists during recursion. We'll present three examples of this in the forthcoming cards.

List Construction Example 1

An example use of list construction is when we wish to create a new list out of two existing lists. We'll illustrate this by defining a predicate called append that takes three arguments. The first two are lists. The predicate uses these two lists to produce a third list which combines the original two. For example,

?- append([a,b,c],[one,two,three],Result).

Result = [a,b,c,one,two,three]

The way we do this in Prolog uses both list construction and list deconstruction. Recall that on the previous card we saw how we could glue an item onto the front of a list to produce a new list. Thus we can produce the list [c,one,two,three] from the list [one,two three] by saying NewList = [c|[one,two,three]. This results in NewList being bound to the list [c,one,two,three]. This is the clue to how we write append in Prolog. We can recursively split the first list into single items by the deconstruction techniques discussed earlier. We can then use the construction method above to glue together a new list, which we shall illustrate next.

List Construction Example 2

In order to write append we shall first search through the first list, and taking each item in turn, add it to the second list. This we'll do recursively, by searching for the end of the first list, and then adding the items in the first list to the items in the second list in reverse order. Thus the last item in the first list is the first to be added to the second list. We illustrate this more clearly with an example. First lets see what the code to do this look like. First we must deal with the case when the first list is an empty list. In this case the result of appending the two lists will just be the second list. Thus this gives

append([],List,List).

Now for the rule which does most of the work. This says search through the first list can each time stick the first thing on the first list onto the resulting list.

append([Head|Tail],List2,[Head|Result]):-

    append(Tail,List2,Result).

Now lets go through in detail how this actual works.

List Construction Example 3

Recall our code and query ?- append([a,b,c],[one,two,three],Result).

append([],List,List).

append([Head|Tail],List2,[Head|Result]):-

    append(Tail,List2,Result).

Let's now follow the program as it executes. Using the second rule we first reduce the query to

append([b,c],[one,two,three],Result)

and then to

append([c],[one,two,three],Result)

and finally to

append([],[one,two,three],Result). 

       

This final clause can match against the initial fact, giving append([],[one,two,three],[one,two,three]). Since this is a fact, this terminates the recursion. As we pop out of each recursive step we then add on (respectively) c,b, and a to the list, giving the list [a,b,c.one,two,three].

List Construction Example 3

Now, we will append again, no doubt, but will append it in a different way.

Write a 3-place predicate combine1 which takes three lists as arguments and combines the elements of the first two lists into the third as follows:

?- combine2([a,b,c],[1,2,3],X).
 X = [a,1,b,2,c,3]
 ?- combine2([foo,bar,yip,yup],[glub,glab,glib,glob],Result).
 Result = [foo,glub,bar,glab,yip,glib,yup,glob]

Take a look at the format of the output variable X. We can have the solution as this-

combine2([],[],[]).

combine2([H1|T1], [H2|T2], [H1,H2|T3]):- combine2(T1,T2,T3).

Now, as you have learnt a lot, we will try to judge ourselves with a lab test

Write a predicate twice(In,Out) whose left argument is a list, and whose right argument is a list consisting of every element in the left list written twice. For example, the query

twice([a,4,buggle],X).

should return

X = [a,a,4,4,buggle,buggle]).

And the query

twice([1,2,1,1],X).

 should return

X = [1,1,2,2,1,1,1,1].

Write a program to replace all occurrences of one item in a list with another. It should have four arguments. The list you wish to use. The item to replace. The item to replace it with, and the resulting list. Here are some example of its behaviour

?- replace_all([a,b,a,c,a,d],a,mike,Result).

Result = [mike,b,mike,c,mike,d]

?- replace_all([a,b,a,c,a,d],b,foo,Result).

Result = [a,foo,a,c,a,d]

?- replace_all([a,b,a,c,a,d],prolog,logic,Result).

Result = [a,b,a,c,a,d]

Write a prolog program to find out the permutations of numbers of a list.

Here is a sample goal for 'perm':

del(X,[X|L1],L1).
    del(X,[Y|L1],[Y|L2]):-
        del(X,L1,L2).
    permute([],[]).
    permute(L,[X|P]):-
        del(X,L,L1),
        permute(L1,P).

?- perm([1,2,3],P).

P = [1,2,3] ;

P = [2,1,3] ;

P = [2,3,1] ;

P = [1,3,2] ;

P = [3,1,2] ;

P = [3,2,1] ;

No