Subject: Re: [SWIPL] Prolog help

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 19 Dec 2000 12:56:03 +1300 (NZDT)

Nuno Baptista <[email-masked]> wrote:

	I've already found a way to intersect lists.
	If anyone wants to use here it is.

	lista([],S,[]). 
	lista(S,[],[]):-
		S\=[]. 
	lista([X|TX],[X|TY],[X|TZ]):- 
		lista(TX,TY,TZ). 
	lista([X|TX],[Y|TY],TZ):- 
		lista(TX,[Y|TY],TZ). 
	lista([X|TX],[Y|TY],TZ):- 
		lista([X|TX],TY,TZ). 

Urk.
 - Why call it 'lista' when it means 'intersection'?
 - Why use five clauses when three will do?
 - Why use something that doesn't actually work?

Here is how you design an intersection predicate.
First, the interface:
    intersection(+As: list(T), +Bs: list(T), -ABs: list(T))
or
    intersection(+As: list(T), +Bs: list(T), ?ABs: list(T))

Then we ask,
 ? can we work down both input arguments in a single recursion?
	NO.  We are not told that the elements are in compatible
	orders.
 ? does it matter which of the input arguments we try recurring on?
	NO.  The problem is symmetric, so we can break the symmetry either way.
 ? what are the cases?
	Sets are represented by lists.  Sets (and lists) may be empty or not.
 ? what is the first case?
	It is an excellent rule to start with the base case.
	The base case here is "As is empty".
 ? in the first case, what else do we need to know?
	Nothing.  The intersection of an empty set with Bs is empty,
	whatever Bs may be.
 + We now have our first clause.
	intersection([], _, []).
 ? what is the second case?
	We have a non-empty set represented by a non-empty list.
	Call it [A|As].
 ? what else do we need to know?
	Whether the list element we have easy access to (A) should be
	included in the result or not.
 ? how do we decide that?
	if A is a member of the second argument, it is part of the
	intersection, otherwise it isn't.
 ? How do we implement that test?
	There is a predicate member/2 we can call.
	(There should also be memberchk/2 and nonmember/2.)
	Let's try member(A, Bs).
 ? How do we use that test
	When there is a two-way decision to make, we could do
	    p(...) :- cond, !, ..t..
	    p(...) :- /*~cond*/, ..f..
	or
	    p(...) :- \+ cond, !, ..f..
	    p(...) :- /*cond*/, ..t..
	or
	    p(...) :- (cond -> ..t.. ; ..f..).
	or
	    p(...) :- (\+cond -> ..f.. ; ..t..)
 ? is there a reason to prefer one to the others?
        We want to do different output unifications in the two cases,
        so the code may be prettier if we use two clauses rather than
        if-then-else.
 ? What are the candidates now?

	intersection([], _, []).
	intersection([A|As], Bs, [A|ABs]) :-
	    member(A, Bs),
	    !,
	    intersection(As, Bs, ABs).
	intersection([_|As], Bs, ABs) :-
	    intersection(As, Bs, ABs).

    and

	intersection([], _, []).
	intersection([A|As], Bs, ABs) :-
	    \+ member(A, Bs),
	    !,
	    intersection(As, Bs, ABs).
	intersection([A|As], Bs, [A|ABs]) :-
	    intersection(As, Bs, ABs).

 ? is there any reason to prefer one of those to the other?
	Yes.  The second one is steadfast.  Guessing wrong about the
	output in the call will not trick it into choosing the wrong
	clause.

Note:  since we have precisely two two-way decisions (is this set empty
or not, is this element in the other set or not), we need three clauses.

	I'm trying to find a way to get the the names of the places
	where a bus goes to

	ligacao has a origin and a list of [destinations, ] like 
	ligacao('Pr. Liberdade',
	    ['Serra Pilar','S. Domingos','Carmo','Av. Aliados']).)
	
Why is it not a table of origin/destination pairs such as

	ligacao('Pr. Liberdade', 'Serra Pilar').
	ligacao('Pr. Liberdade', 'S. Domingos').
	ligacao('Pr. Liberdade', 'Carmo').
	ligacao('Pr. Liberdade', 'Av. Aliados').

Sometimes (as in the intersection/3 example) one *has* to break a problem
symmetry in the code, but it should always make you uneasy to do so.

	autocarro has the numbers of the bus that has a stop in some place : 
		autocarro('Pr.Liberdade',[1,7,91,33,83,15,19,76,54]).
	
Same question.

	the rest of the code is here, but it's not working properly:
	
Yes, but what is it *supposed* to do?

	percurso(Destino,Destino,[]).
	percurso(Origem,Destino,Lista):-
		autocarro(Origem,LA1),
		ligacao(Origem,LO),
		member(NO,LO),
		autocarro(NO,LA2),
		lista(LA1,LA2,L),
		percurso(NO,Destino,L).
	
One thing is pretty obvious.  You have a variable Lista which is never
bound.  What you have seems to be something like this, where I shall
assume simple binary relations

	from_to(From, To)		% ligacao
	place_bus(Place, BusNo)		% autocarro

	route(Place, Place, []).
	route(Place0, Place, [BusNo|Route]) :-
	    from_to(Place0, Place1),
	    place_bus(Place0, BusNo),
	    place_bus(Place1, BusNo),
	    /* BusNo is the number of a bus that goes from Place0 to Place1 */
	    route(Place1, Place, Route).

Of course, there is a problem here.  In many cities, if bus number 7
takes you from George St to Forbury Corner (which it does, it's the
St Clair bus here), then it is also bus number 7 that takes you from
Forbury Corner to George St.  So the graph you are searching has many
cycles in it, which means that even this corrected code will not work
very well.

The solution is clearly explained in "Programming in Prolog", by
Clocksin & Mellish, and most other Prolog textbooks too.  RTFTB.