Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!sun!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Higher Order Extensions
Message-ID: <996@quintus.UUCP>
Date: 14 Apr 89 04:07:45 GMT
References: <11500013@hpldola.HP.COM>
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 32

In article <11500013@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes:
>This may explain why _The_Art_of_Prolog_ (section 17.2) suggests that
>you `need' both extensions for the breadth-first search of possibly
>cyclic graphs.  In their example, they encode the graph into the program
>as the edge/2 relation.  If the graph were instead represented as a data
>structure, then I maintain that the extensions would be unnecessary.

There is an intermediate representation:
	start(WhereToStartTheSearch).
--->	children(Node, SetOfAllThatNodesChildren).
	solution(X) :- X is a node which has what we're looking for.

In effect,
	children(Node, Children) :-
		set_of_all(Child, edge(Node,Child), Children).
With that representation, breadth-first search can be done in 4 pure
(slightly obfuscated) Horn clauses:

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

breadth_star([], s(_), [Answer|_], [], Answer) :-
	solution(Answer).
breadth_star([], s(N), [X|F], B, Answer) :-
	children(X, Children),
	breadth_star(Children, N, F, B, Answer).
breadth_star([X|Xs], N, F, [X|B], Y) :-
	breadth_star(Xs, s(N), F, B, Y).

It is worth noting that iterative deepening is competitive with
breadth first search in Prolog.