Is there a Common Lisp function that detects whether or not a list is
circular?
Here is an example of what I mean by circular:
(setq x '(1 2))
(setf (cadr x) x)
x
=> (1 (1 (1 (1 (1 .....)))
Is there a function that I can call on x that will tell me if the list
is circular?
Thanks in advance.
·········@ptcstudios.com
········@ptcstudios.com writes:
>
> Is there a Common Lisp function that detects whether or not a list is
> circular?
>
> Here is an example of what I mean by circular:
> (setq x '(1 2))
> (setf (cadr x) x)
> x
> => (1 (1 (1 (1 (1 .....)))
>
> Is there a function that I can call on x that will tell me if the list
> is circular?
>
> Thanks in advance.
Yes and no.
First, the problem is that circularity occurs potentially along many
paths. Objects may print with a circularity and not be considered
circular.
For example, a structure may have a backpointer to itself and yet not
be considered circular with respect to cons cells.
You should probably set *PRINT-CIRCLE* to T if you have a worry of
such things, and it will make the above print more nicely, as in:
#1=(1 #1#). But you'll note that if you do:
(defstruct kons kar kdr)
(setq x (make-kons 1 (make-kons 2 nil)))
(setf (kar (kdr x)) x)
x
=> #1=#S(KONS KAR 1 KDR #S(KONS KAR #1# KDR NIL))
or something like that. [I didn't bother to test this; I'm just
guessing. So your mileage might vary slightly if I screwed up.]
Anyway, Lisp considers this to be an "atomic" expression and so logically
no more circular than if you'd done:
(setf (get 'a 'b) 'a)
which if you saw as a "structure" might print as
#1=#S(SYMBOL NAME "A" PLIST (#S(SYMBOL NAME "B") #1#))
and yet most people don't regard that as circular. Early AI programmers
figured out quickly that symbols and their property lists were good ways
to hide circularity, before we had *print-circle*, and so lots of AI stuff
uses symbol relationships like this so it can be read/written from files
successfully even with printers that supposedly don't handle "circularity".
If you're looking specifically for "list"` circularity, the list you
specified is not circular--it is 2 elements long. (That is, the
circularity you describe is on a path through a tree. When you deal
with stuff like this, it's important to understand that there is a
rich need for terminology because there is a rich set of possible
things that people consider "circular" which are really not related,
or at least which are not directly related and which slow you down if
you must check for them.)
You can call list-length on that list and see this. It would return
NIL if the list WERE circular.
Circularity can be detected in a variety of ways. You could write a
tree-walker, for example, that would detect circularity by each time
checking a hash table for previously seen conses and then descending
each side of the conses, recording the cons in the table, until you
bottomed out. At the first collision, you'd know you had a circularity.
There is also a cute algorithm in which you define a path through a
structure and you start two "runners" down that path, one proceeding
twice as fast as the other. If the fast runner ever catches up to the
slow runner, you know you have a circularity. I think this is what
list-length typically does, because this algorithm works well in
conjunction with operations like LENGTH. The fast runner accumulates
the length as he goes, and if he hits the end of the list before he
catches the slow one, he returns the LENGTH.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>...
>
>There is also a cute algorithm in which you define a path through a
>structure and you start two "runners" down that path, one proceeding
>twice as fast as the other. If the fast runner ever catches up to the
>slow runner, you know you have a circularity. I think this is what
>list-length typically does, because this algorithm works well in
>conjunction with operations like LENGTH. The fast runner accumulates
>the length as he goes, and if he hits the end of the list before he
>catches the slow one, he returns the LENGTH.
I think that trick is in knuth vol 1 (1968?) in an exercise.
P and Q, one jumping over every other node, the other
not? Was it something like that?
David
·······@netcom.com (David Combs) writes:
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> >There is also a cute algorithm in which you define a path through a
> >structure and you start two "runners" down that path, one proceeding
> >twice as fast as the other. If the fast runner ever catches up to the
> >slow runner, you know you have a circularity. [...]
>
> I think that trick is in knuth vol 1 (1968?) in an exercise.
>
> P and Q, one jumping over every other node, the other
> not? Was it something like that?
Sounds like the same one. My Knuth's are in a box, so can't check.
I just learned it from a friend. Note, of course, that the algorithm
is easy to modify so that the "nodes" are "any path", so if you want to
look for car or cadr circularities instead of cdr circularities, you
just separately define the path and send your runners running.
It's pretty much intuitively obvious that if you run ahead and bump
into something slower, you've gone in a circle. I vaguely remember
an apropos limerick...
There once was a a man from [???]
Who said he could run faster than light. [<--bad meter, probably a bug here]
He set out one day
In a relative way
And returned on the previous night.
Ah well..
Kent wrote:
> It's pretty much intuitively obvious that if you run ahead and bump
> into something slower, you've gone in a circle. I vaguely remember
> an apropos limerick...
>
> There once was a a man from [???]
> Who said he could run faster than light. [<--bad meter, probably a bug here]
> He set out one day
> In a relative way
> And returned on the previous night.
I think the usual version begins:
There was a young lady named Bright,
Who travelled much faster than light.
(The other three lines are as you gave them, mutatis mutandis.)
--
Gareth McCaughan ················@pobox.com
sig under construction
Gareth McCaughan wrote:
>
> Kent wrote:
> > There once was a a man from [???]
> > Who said he could run faster than light. [<--bad meter, probably a bug here]
> > He set out one day
> > In a relative way
> > And returned on the previous night.
>
> I think the usual version begins:
>
> There was a young lady named Bright,
> Who travelled much faster than light.
>
> (The other three lines are as you gave them, mutatis mutandis.)
It has a sequel:
Now this lady was Bright but not bright
And she joined in next day on the flight
So two made the date
And then four and then eight
And her spouse got a hell of a fright
--
"To summarize the summary of the summary: people are a problem."
Russell Wallace
···············@esatclear.ie
http://www.esatclear.ie/~rwallace
Russell Wallace <········@esatclear.ie> writes:
> It has a sequel:
>
> Now this lady was Bright but not bright
> And she joined in next day on the flight
> So two made the date
> And then four and then eight
> And her spouse got a hell of a fright
Cute. (Moral: When dealing with circular lists,
don't forget the termination condition.)
Kent M Pitman <······@world.std.com> writes:
> Cute. (Moral: When dealing with circular lists,
> don't forget the termination condition.)
or: don't marry fast women... ?
thi
In article <···············@world.std.com>, Kent M Pitman
<······@world.std.com> wrote:
>·······@netcom.com (David Combs) writes:
>> In article <···············@world.std.com>,
>> Kent M Pitman <······@world.std.com> wrote:
>> >There is also a cute algorithm in which you define a path through a
>> >structure and you start two "runners" down that path, one proceeding
>> >twice as fast as the other. If the fast runner ever catches up to the
>> >slow runner, you know you have a circularity. [...]
>>
>> I think that trick is in knuth vol 1 (1968?) in an exercise.
>>
>> P and Q, one jumping over every other node, the other
>> not? Was it something like that?
>
>Sounds like the same one. My Knuth's are in a box, so can't check.
>I just learned it from a friend. Note, of course, that the algorithm
>is easy to modify so that the "nodes" are "any path", so if you want to
>look for car or cadr circularities instead of cdr circularities, you
>just separately define the path and send your runners running.
>
>It's pretty much intuitively obvious that if you run ahead and bump
>into something slower, you've gone in a circle. I vaguely remember
>an apropos limerick...
>
> There once was a a man from [???]
> Who said he could run faster than light. [<--bad meter, probably a bug here]
> He set out one day
> In a relative way
> And returned on the previous night.
There was a young lady named Bright
Whose speed was much faster than light...
It's intuitively obvious, but for some reason until this
particular explanation the whole thing had eluded me.
thanks.
··@panix.com (Paul Wallich) writes:
> In article <···············@world.std.com>, Kent M Pitman
> <······@world.std.com> wrote:
>
> >It's pretty much intuitively obvious that if you run ahead and bump
> >into something slower, you've gone in a circle. I vaguely remember
> >an apropos limerick...
> >
> > There once was a a man from [???]
> > Who said he could run faster than light. [<--bad meter, probably a bug here]
> > He set out one day
> > In a relative way
> > And returned on the previous night.
>
> There was a young lady named Bright
> Whose speed was much faster than light...
>
> It's intuitively obvious, but for some reason until this
> particular explanation the whole thing had eluded me.
>
> thanks.
The most humerous example I recall was an Alphaville album. At the
start of the A side, before the start of any music, one heard the word
'night'. At the end of the B side, after all the music, was:
There once was a woman from Bright
Who could travel much faster than light
She left one day
In a relative way
And returned the previous . . .
Thom
--
Scientist ···@cra.com
Charles River Analytics (617) 491-3474 x574
Cambridge, MA, USA http://www.cra.com/
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
> ·······@netcom.com (David Combs) writes:
> > In article <···············@world.std.com>,
> > Kent M Pitman <······@world.std.com> wrote:
> > >There is also a cute algorithm in which you define a path through a
> > >structure and you start two "runners" down that path, one
proceeding
> > >twice as fast as the other. If the fast runner ever catches up to
the
> > >slow runner, you know you have a circularity. [...]
> >
> > I think that trick is in knuth vol 1 (1968?) in an exercise.
> >
> > P and Q, one jumping over every other node, the other
> > not? Was it something like that?
>
> Sounds like the same one. My Knuth's are in a box, so can't check.
> I just learned it from a friend. Note, of course, that the algorithm
> is easy to modify so that the "nodes" are "any path", so if you want
to
> look for car or cadr circularities instead of cdr circularities, you
> just separately define the path and send your runners running.
It seems to me that this algorithm, which works well for detecting
cdr-circularities, is not easily generalizable to arbitrary structures.
Consider applying this function with the hare and the tortoise to the
result of (fumo 10), where fumo is defined as:
(defun fumo (n)
(do ((n n (- n 1))
(fumo '() (cons fumo fumo)))
((zerop n) fumo)))
certainly the two cursors will meet somewhere, but (fumo 10) is not
circular in any way.
If someone knows a solution without the table, I'd like to hear about
it!
--
Pierpaolo Bernardi
Sent via Deja.com http://www.deja.com/
Before you buy.
·········@my-deja.com writes:
> It seems to me that this algorithm, which works well for detecting
> cdr-circularities, is not easily generalizable to arbitrary structures.
>
> Consider applying this function with the hare and the tortoise to the
> result of (fumo 10), where fumo is defined as:
>
> (defun fumo (n)
> (do ((n n (- n 1))
> (fumo '() (cons fumo fumo)))
> ((zerop n) fumo)))
>
> certainly the two cursors will meet somewhere, but (fumo 10) is not
> circular in any way.
>
> If someone knows a solution without the table, I'd like to hear about
> it!
I don't understand. If you replace CDR in the algorithm with
(FUNCALL CDR-SUBSTITUTE X) then any path you run on has to be possible to
do in exactly the same way, given a specific CDR-SUBSTITUTE.
Note that the algorithm I'm talking about uses *no* table. It is
simply dependent on the two runners using the same algorithm to find
the next state given the current state, and one getting twice as many
pulses between stops to look. It does not remember where it has been,
and so you don't find the circularity when you land on a previously
visited node. (If I recall, you're guranteed to find it in some fairly
bounded time, though; I think it's the length of the non-circular portion
plus a small multiplier times the length of the circularity.) As such,
I can't imagine it being faked out by fumo thing. I suppose I could just
write out the algorithm, it's so simple, but I was leaving it as an exercise
for someone else to do it since I've done it a number of times before.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
> ·········@my-deja.com writes:
>
> > OK, what I was thinking of is the following (Sorry, scheme is the
only
> > thing I have available here):
> >
> > ;;; WARNING: does not work!
> >
> > (define (has-cycles? sexpr)
> > (let ((end (list 'end))) ; A unique marker
> > (define (enumerator sexpr)
> > (let ((stack (list sexpr)))
> > (lambda ()
> > (if (null? stack)
> > end
> > (let ((head (pop! stack)))
> > (when (pair? (cdr head))
> > (push! (cdr head) stack))
> > (when (pair? (car head))
> > (push! (car head) stack))
> > head)))))
> > (let ((slow (enumerator sexpr))
> > (fast (enumerator sexpr)))
> > (fast)
> > (let loop ()
> > (let ((a (slow))
> > (b (fast)))
> > (cond ((eq? b end) #f)
> > ((eq? a b) #t)
> > (else (if (eq? (fast) end)
> > #f
> > (loop)))))))))
> >
> > Now, if sexpr has cycles, the functions returns True. If sexpr is a
> > tree, the functions returns false. The problems arises when sexpr
is a
> > dag (as is the case with (fumo 10), In this case, the answer is
random.
>
> Oh sigh. We are probably talking at crossed purposes.
Most definitely.
> I don't see
> what all that stack stuff is for in the above, and I'm not going to
> try to figure it out because it doesn't address the algorithm I was
> speaking about..
If I remember correctly the thread, you talked about the function for
detecting cdr-circularities in a list, and I know this one. Then you
added that this technique could be easily generalized to detect
circularities in a general graph.
Just by coincidence, few days ago I asked to myself the same question,
i.e. whether is possible to detect cycles in a graph using constant
storage. I have not found an answer to *that* question. The best I
could do is my function HAS-CYCLES?, which is flawed.
> ;; I'm not sure what your fumo example is supposed to show,
Is an example which breaks MY function. Your function addresses a
different problem.
> (defun fumo (n)
> (do ((n n (- n 1))
> (fumo '() (cons fumo fumo)))
> ((zerop n) fumo)))
>
> (circularp (fumo 10)) => nil
And this is correct.
However, the original poster asked for a function that could detect this
circularity:
|Here is an example of what I mean by circular:
| (setq x '(1 2))
| (setf (cadr x) x)
Your function fails here.
> don't do much programming in scheme these days, though, so I could
> easily have screwed up some detail. Caveat emptor.
No problem.
--
Pierpaolo Bernardi
Sent via Deja.com http://www.deja.com/
Before you buy.
* oloapreip wrote:
> Just by coincidence, few days ago I asked to myself the same question,
> i.e. whether is possible to detect cycles in a graph using constant
> storage. I have not found an answer to *that* question. The best I
> could do is my function HAS-CYCLES?, which is flawed.
Now you ask this explicitly I believe that the answer is `no'. This
is what prolog people call an `occurs check' and I think it's known to
be linear in the size of the graph you are checking. But I could be
wrong.
--tim
·········@my-deja.com writes:
> If I remember correctly the thread, you talked about the function for
> detecting cdr-circularities in a list, and I know this one. Then you
> added that this technique could be easily generalized to detect
> circularities in a general graph.
I didn't say in a general graph, I said along an arbitrary path. The key
is that you specify the path. This algorithm is specific to linear
situations and would break down if runners could pass each other. If you
can linearize the graph into a path, then this algorithm will reliably detect
circularity and not otherwise.
> Just by coincidence, few days ago I asked to myself the same question,
> i.e. whether is possible to detect cycles in a graph using constant
> storage. I have not found an answer to *that* question. The best I
> could do is my function HAS-CYCLES?, which is flawed.
I don't doubt that I have an indadequate understanding of some
relevant field of study like topology in order to fairly answer this.
However, it seems to me that the true answer must be caught up in the
notion of what "here" means in situations involving shared structure.
The idealized "path world" for which the algorithm is designed does
not have the notion of "shared structure", other than circularity, in
the sense that "being at an eq point" is really identical in meaning
to "having detected a circularity". To give it another meaning, you'd
have to say that a position is defined by the set of moves you take in
order to reach it, but that would mean that a circular list was not
circular because the hare took a different set of moves to reach the
"same" spot as the tortoise did. This playing fast and loose with the
terminology is almost surely what's at the heart of the problem.
> However, the original poster asked for a function that could detect this
> circularity:
>
> |Here is an example of what I mean by circular:
> | (setq x '(1 2))
> | (setf (cadr x) x)
>
> Your function fails here.
Well, mine is capable of detecting it, given the :path-fn #'cadr argument
so that it knows that the path you care about is the cadr path. Mine
is not doing the Star-Trek-ian "I'm transmitting on all frequencies" magic
where it magically enumerates all possible values for :path-fn and tries
them in finite time.
In article <······························@g.local>,
················@pobox.com wrote:
> Pierpaolo Bernardi wrote:
> > > > It seems to me that this algorithm, which works well for
detecting
> > > > cdr-circularities, is not easily generalizable to arbitrary
> > > > structures.
> > > >
> > > > Consider applying this function with the hare and the tortoise
to
> > > > the result of (fumo 10), where fumo is defined as:
> > > >
> > > > (defun fumo (n)
> > > > (do ((n n (- n 1))
> > > > (fumo '() (cons fumo fumo)))
> > > > ((zerop n) fumo)))
> > > >
> > > > certainly the two cursors will meet somewhere, but (fumo 10) is
not
> > > > circular in any way.
> ..
> > OK, what I was thinking of is the following (Sorry, scheme is the
only
> > thing I have available here):
> [SNIP: "has-cycles?" definition]
> > Now, if sexpr has cycles, the functions returns True. If sexpr is a
> > tree, the functions returns false. The problems arises when sexpr
is a
> > dag (as is the case with (fumo 10), In this case, the answer is
random.
I should have written: ... when sexpr is a DAG that is not a tree, to
make sense. That is, when there are shared nodes, but no cycles. Sorry.
> > If I'm overlooking an easy solution, I'd like to know it!
>
> Your HAS-CYCLES? function is considerably more complicated
> than the usual, though I think that's mostly a result of
> doing it in Scheme style.
>
> (defun has-cycles (list)
> (loop for slow = (cdr list) then (cdr slow)
> for fast = (cddr list) then (cddr fast)
> when (endp fast)
> return nil
> when (eq slow fast)
> return t))
My functions tried to solve a different problem.
> This will happily return NIL (clearly the correct answer) on
> the result of your FUMO function. If what you want is a function
> that will determine whether or not a given sexpr is a tree,
> you do need a table;
Certainly. But Kent Pitman suggested that it could be done without the
table, so my curiosity was awakened.
--
Pierpaolo Bernardi
Sent via Deja.com http://www.deja.com/
Before you buy.
Pierpaolo Bernardi wrote:
[I said:]
> > This will happily return NIL (clearly the correct answer) on
> > the result of your FUMO function. If what you want is a function
> > that will determine whether or not a given sexpr is a tree,
> > you do need a table;
>
> Certainly. But Kent Pitman suggested that it could be done without the
> table, so my curiosity was awakened.
I don't think he did suggest that. I think he suggested that
you can detect particular kinds of cycle other than ones on
the CDR (for instance, circularities as you chain along the
CARs in an s-expression). Not that the same algorithm can
detect arbitrary circularities.
--
Gareth McCaughan ················@pobox.com
sig under construction
In article <···············@world.std.com>, Kent M Pitman
<······@world.std.com> wrote:
>> >There is also a cute algorithm in which you define a path through a
>> >structure and you start two "runners" down that path, one proceeding
>> >twice as fast as the other. If the fast runner ever catches up to the
>> >slow runner, you know you have a circularity. [...]
>>
>> I think that trick is in knuth vol 1 (1968?) in an exercise.
It's also in Structur and Implementation of Computer Programs, again as
an exercise (but with solution).
Neil
Neil Cohen
Bridge Trix
Producers of the Bobby Wolff Bridge Mentoring Series
·······@netcom.com (David Combs) writes:
> In article <···············@world.std.com>,
> Kent M Pitman <······@world.std.com> wrote:
> >...
> >
> >There is also a cute algorithm in which you define a path through a
> >structure and you start two "runners" down that path, one proceeding
> >twice as fast as the other. If the fast runner ever catches up to the
> >slow runner, you know you have a circularity. I think this is what
> >list-length typically does, because this algorithm works well in
> >conjunction with operations like LENGTH. The fast runner accumulates
> >the length as he goes, and if he hits the end of the list before he
> >catches the slow one, he returns the LENGTH.
>
> I think that trick is in knuth vol 1 (1968?) in an exercise.
>
> P and Q, one jumping over every other node, the other
> not? Was it something like that?
Almost. The "turtle" skips every other move, not every other node.
--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Some vocal people in cll make frequent, hasty personal attacks, but if
you killfile them cll becomes usable.
* ········@ptcstudios.com
| Is there a Common Lisp function that detects whether or not a list
| is circular?
The function list-length returns the length of a proper list, or nil
when applied to a circular list.
#:Erik
--
If this is not what you expected, please alter your expectations.