next up previous
Next: Useful Tip 5 Up: Efficiency Considerations Previous: Useful Tip 3

Useful Tip 4

Don't use cuts indiscriminately. Here is an example taken from O'Keefe, ``The Craft of Prolog''. The plan is to define a predicate, match1/2, which will take as its first argument a pattern for a sequence (with some ``holes'' in it) and take as its second argument a complete sequence of symbols. The predicate should succeed if the pattern can be matched to the sequence. For example:

| ?- match1([i,X,my,Y], [i,like,my,lecturing,job]).
X = [like],
Y = [lecturing,job]
One way to define it is as follows:
match1([], []).
match1([H|T], [F|R]):-
    nonvar(H), !,
    H = F,
    match1(T, R).
match1([V|T], [F|R]):-
    match1(T, R),
    V = [F].
match1([V|T], [F|R]):-
    match1([New|T], R),
    V = [F|New].
This works, but is not as fast as the following definition, named match2/2, which has no cuts but distinguishes the type of symbol in the pattern list using w(X), if X is a word, and s(X), if X is a segment of the sequence.
match2([], []).
match2([H|T], [F|R]):-
    match2(H, T, F, R).

match2(w(Word), Items, Word, Words):-
    match2(Items, Words).
match2(s([Word|Seg]), Items, Word, Words0):-
    append(Seg, Words1, Words0),
    match2(Items, Words1).
The behaviour of this predicate is as follows:
| ?- match2([w(i),s(X),w(my),s(Y)], [i,like,my,lecturing,job]).
X = [like],
Y = [lecturing,job]

Dave Stuart Robertson
Tue Jul 7 10:44:26 BST 1998