Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!turpin
From: turpin@cs.utexas.edu (Russell Turpin)
Newsgroups: comp.lang.prolog
Subject: Another question on pointers and Prolog.
Message-ID: <18129@cs.utexas.edu>
Date: 25 Feb 91 22:19:08 GMT
Organization: UTexas CS Dept, Austin, Texas
Lines: 30

-----
Some variants of Prolog support "infinite" data structures, that
is, non-tree-like data structures.  (In essence, an "infinite"
data structure is repetitive and there is a folding of it onto the
underlying finite, non-tree-like data structure.  Thus, the
following cyclic list:

	a --> b --> c -+
	      ^        |
	      +--------+

is equivalent to the "infinite" data structure abcbcbcbc ...)

A common problem given to undergraduates in a data structures
class is this: given a list, determine in linear time and constant
(pointer size) space whether the list terminates (ends in a null
pointer) or cycles.  The solution is to advance two pointers down
the list, one at twice the rate of the other, until either (1)
they are equal, indicating a cycle, or (2) the faster one falls
off the list.

Now suppose one is writing a Prolog program that deals with a
potentially infinite (cyclic) list, and one desires a predicate
that tests a list to determine whether it is infinite (cyclic).
How would one implement an efficient test such as the algorithm
described above? 

Alternatively, if one must either rely on built-in primitives or
a less efficient algorithm, should this be seen as a problem?

Russell