Re: [Caml-list] Recursive lists

[Alex Baretta <alex@baretta.com>]

Ville-Pertti Keinonen wrote:
> William Lovas wrote:
> 
>> On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:
>>
> This can be fixed by comparing the list node pointers rather than the 
> contents.  I'm sure Brian meant the match in the above to look like:
> 
> match p1, p2 with
>  | (_ :: t1), (_ :: (_ :: t2) as p3) ->
>    if p1 == p2 or p1 == p3 then
>      true
>    else
>      loop t1 t2
>  | _ -> false
> 
>> ... and this isn't it :)  I think Alex was more on the right track 
>> with the
>> idea of maintaining a list of tails...
>>  
>>
> There's no need for such a thing, at least for determining circularity, 
> the "tortoise and hare" algorithm is well-known and works just fine, as 
> long as it's implemented correctly.

You can't say that there is no need for it. Think of a monadic 
composition of this algorithm with a list traversal which actually gets 
some work done. The need to maintain the list of tails appears in this 
context, where I know that only *some tails* are worth stacking into the 
cycle detection list, depending on the result of processing the single node.

Besides the tortoise and hare algorithm is not really any better than 
mine, at least in terms of asymptotic worst case complexity, except that 
it allocates less.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners