Re: [Caml-list] Recursive lists

[William Lovas <wlovas@stwing.upenn.edu>]

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

> [...]
>
> Note: I haven't tested the above functions, but they give you the idea of 
> how to handle circular lists.

... and this isn't it :)  I think Alex was more on the right track with the
idea of maintaining a list of tails...

cheers,
William

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