Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: A little template matcher
Message-ID: <3448@goanna.cs.rmit.oz.au>
Date: 20 Jul 90 09:28:26 GMT
References: <2994@skye.ed.ac.uk>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 50

In article <2994@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes:
> % A simple template matcher.

> match([], []).
> match([X1|T1], Text) :-
> 	matchv(X1, A-A, T1, Text).
> match([X1|T1], [X2|T2]) :-	% The nonvar avoids extra solutions in
> 	nonvar(X1),		% cases like match([X,b,c],[a,b,c])
> 	match(T1, T2),		% by avoiding the solution X=a
> 	X1 = X2.		% (X=[a] is the only solution intended)

> matchv(Stuff, Stuff-[], Template, Text) :-
> 	match(Template, Text).
> matchv(X, Stuff-[Word|A], Template, [Word|Text]) :-
> 	matchv(X, Stuff-A, Template, Text).

The first thing to notice about this is that it uses an explicit
"difference list" data structure.  Ugh.  There is just no point in
packaging two things up just in order to unwrap them again in the
very next instant.  We can simplify this to

match([], []).
match([X1|T1], Text) :-			% X1 is a list or a variable
	matchv(X1, A, A, T1, Text).
match([X1|T1], [X2|T2]) :-		% X1 is an atom
	nonvar(X1),
	X1 = X2,
	match(T1, T2).

matchv(Stuff, Stuff, [], Template, Text) :-
 	match(Template, Text).
matchv(X, Stuff, [Word|A], Template, [Word|Text]) :-
 	matchv(X, Stuff, A, Template, Text).

This might be more clearly expressed as

	match([], []).
	match([Item|Items], [Word|Words) :- atom(Item), Item \== [], !,
		Item = Word,
		match(Items, Words).
	match([Item|Items], Words) :-
		append(Item, RestWords, Words),
		match(Items, RestWords).

The trouble with this, of course, is that it is still rather non-logical.
See pages 150--152 of "The Craft of Prolog" for a pure (=faster) version.

-- 
Science is all about asking the right questions.  | ok@goanna.cs.rmit.oz.au
I'm afraid you just asked one of the wrong ones.  | (quote from Playfair)