🚀 go-pugleaf

In article <2207@zodiac.UUCP>, jdevries@zodiac.ads.com (Jeff De Vries) writes:
> I needed to do a breadth-first search in Prolog, so being the naturally lazy
> person that I am, I started to look through some Prolog books to see if they
> had an example program I could just copy.  I noticed that one author used 
> lists to maintain which nodes still needed to be expanded, while another
> author used assert/1 (and retract/1) to maintain those nodes.  Since I am
> not into Prolog internals, I was wondering about the ramifications of the two
> approaches.  Is one approach going to be, in general, faster than the other,
> (my gut feeling is that the list approach would be faster, but...)?  Are there
> occasions where dynamic assertions are the way to go?  Are there things that
> you can do with assertions that you can't do with lists?
> 
It all depends on what you want to do.  If you *can* do what you want
without changing the data-base, you would be well advised to do so.
Speed ratios of 1000:1 (data-base hacking slower than list processing)
are not uncommon, if you are using a decent compiler.

It would be interesting to hear which book suggested using lists
(I hope you mean queues or difference lists) and which book suggested
using the data base.  Give the second book to a friend.  Better yet,
give it to an enemy (:-).

The one thing that you can do by hacking the data base that you can't
do with a pure approach is maintain information which will survive
across backtracking, but if you really are doing a search you probably
don't want that.

Suppose we are given three predicates:
	start(Position)		- the initial position
	solution(Position)	- tests whether X is a solution
	children(Position, Children)	- returns the children of a position

Here is a version of breadth-first search, due to Fernando Pereira.
It is pure and robust.  I've obfuscated it a bit, because I'm writing
up how to do several sorts of searches in Prolog, and I don't want to
put all that explanation here.

breadth_first(Answer) :-
        start(Start),
        breadth_star(s(0), [Start|Rest], Rest, Answer),
        solution(Answer).

%   breadth_start(LengthOfQueue, HeadOfQueue, TailOfQueue, Answer)

breadth_star(s(N0), [X|F], B0, Y) :-
        (   Y = X
        ;   children(X, Children),
            queue_last_list(Children, N0, B0, N1, B1),
            breadth_star(N1, F, B1, Y)
        ).

queue_last_list([], N, B, N, B).
queue_last_list([X|Xs], N0, [X|B0], N, B) :-
        queue_last_list(Xs, s(N0), B0, N, B).