Re: [Caml-list] Recursive lists

[Ville-Pertti Keinonen <will@exomi.com>]

William Lovas wrote:

>On Sun, Oct 10, 2004 at 07:44:25PM -0500, Brian Hurt wrote:
>  
>
>>You can detect circular lists in O(N) thusly:
>>
>>let is_circular lst =
>>    let rec loop p1 p2 =
>>        match p1, p2 with
>>            | (a :: t1), (b :: c :: t2) ->
>>                if (a == b) || (a == c) then
>>                    true
>>                else
>>                    loop t1 t2
>>            | _ -> false
>>    in
>>    match lst with
>>        | _ :: t -> loop lst t
>>        | [] -> false
>>;;
>>    
>>
>
># is_circular [true; true; true];;
>- : bool = true
>  
>
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.

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