🚀 go-pugleaf

-----
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