Processing lists in Prolog - 2 - University of Birmingham

[Pages:32]06-25433 ? Logic Programming

Processing lists in Prolog - 2

This lecture shows that techniques introduced before (analysing terminating conditions and recursive programming) can be used to develop more complex procedures.

06-25433 ? Logic Programming

This lecture is about:

? writing procedures with one or more terminating or recursive clauses;

? deleting one or all instances of an element from a list;

? The effects of matching v. unification; ? changing the order in which solutions are

presented by changing clause order.

8 - Processing lists in Prolog: 2

1

06-25433 ? Logic Programming

Last time: Terminating at the end of the list

For instance counting all elements:

Terminates at the

% 1 - terminating

end of the list.

count_elem([], Total, Total).

% 2 - recursive

count_elem([Hd|Tail], Sum, Total) :-

Sum1 is Sum + 1,

count_elem([Hd|Tail], Sum1, Total).

8 - Processing lists in Prolog: 2

2

06-25433 ? Logic Programming

Last time: Terminating when given element is found

For instance finding a given element:

% 1 - terminating elem(Elem, [Elem|_]). % 2 - recursive elem(Elem, [_|Tail]) :-

elem(Elem, Tail).

Terminates before the end of the list.

Notice, this can be run "backwards" to enumerate the

individual elements of a list.

Demo1

8 - Processing lists in Prolog: 2

3

06-25433 ? Logic Programming

Last time: Terminating when given number of elements have been scanned

% 1 ? recursive nth(Count, Item, [_|Tail]) :-

Count > 1, Count0 is Count - 1, nth(Count0, Item, Tail).

% 2 ? terminating nth(1, Head, [Head|_]).

8 - Processing lists in Prolog: 2

The code counts down from the given position to 1.

Demo2

4

06-25433 ? Logic Programming

Consolidation moment

Three main ways to halt recursion in list processing:

1. at the end of the list ([]); 2. when a specific element is found; 3. when a specific position in a list is reached.

8 - Processing lists in Prolog: 2

5

06-25433 ? Logic Programming

More than one recursive clause

We've seen an example with two recursive clauses:

classify([], [], []).

classify([Head|Tail], [Head|Numbers], Atoms) :-

number(Head), classify(Tail, Numbers, Atoms).

classify([Head|Tail], Numbers, [Head|Atoms]) :-

atom(Head), classify(Tail, Numbers, Atoms).

8 - Processing lists in Prolog: 2

6

06-25433 ? Logic Programming

More than one terminating clause - 1

It is sometimes necessary to have more than one terminating clause.

Consider the task of pairing the elements of two lists with any elements left over added to the end of the list:

| ?- pair([ann,bel], [joe,bob,sam], Res).

Res = [,,sam] ? ;

no

8 - Processing lists in Prolog: 2

7

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download