This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[Caml-list] Recursive lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2004-10-11 (06:52) From: Ville-Pertti Keinonen Subject: Re: [Caml-list] Recursive lists
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