Re: Question on tree-walking and mutually-recursive types

[Michael Matz <matz at suse dot de>]

Hi,

On Tue, 29 Jun 2004, Joseph S. Myers wrote:

> On Tue, 29 Jun 2004, Michael Matz wrote:
> 
> > ???  This tests if list_{2j+1} or list_{2j+2} equals list_j.  Hence it 
> > doesn't detect cycles.  Cf list == {1,2,3,1}
> 
> Take j=n-1 for for a cycle of period n.

Either I'm dense or your and mine definition of cycles differ quite a bit.

My list is actually the shortest counter-example.  Zack's code would have
q on '1' and p on '2' then '3', then it advances q to '2' and p to '1'
which is the last step.  Never is '1' and '1' compared.

I don't see how this loop will work, except when heavily changed to 
basically do the O(n*2) every-element to every-element test (for instance 
by restarting p's list walk after it ended, _then_ advancing q and 
breaking the loop on q being at end; some optimizations possible).  For 
instance q stops after half of lists elements, so if the cycle is in the 
second half it also never sees it.

The loop _only_ works when the cycle forming elements are at index j and
2*j+1 and 2*j+2 (and especially if j<length(list)), which is not my
definition of cycle.  In this case they happen to be at index 0 and 3.

Without additional storage cycle finding can't be O(n).


Ciao,
Michael.