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 (00:36) From: Brian Hurt Subject: Re: [Caml-list] Recursive lists
```

On Fri, 8 Oct 2004, Keith Wansbrough wrote:

>
> > Can some functions of the List library support the use of the recursive
> > lists?
> > I mean: can some scanning functions such as map, for_all, exists, mem,
> > filter, and so on understand if they are working on recursive lists and
> > act correctly without going in buffer overflow or infinite loops?
>
> How could they do this?  It's just a list; there's nothing special
> about it, except that it has no end.

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

let circular_part lst =
let rec find_an_element p1 p2 =
(* find an element in the circular part of the list *)
match p1, p2 with
| (a :: t1), (b :: c :: t2) ->
if (a == b) || (a == b) then
p1
else
find_and_element t1 t2
| _ -> []
in
let find_circular_length lst =
(* find the number of elements in the circular part of the list *)
let rec loop c p =
if lst == p then
c
else
match p with
| _ :: t -> loop (c+1) t
| [] -> 0
in
match lst with
| _ :: t -> loop 1 t
| [] -> 0
in
let rec nth_tail cnt lst =
if cnt == 0 then
lst
else
nth_tail (cnt-1) (List.tl lst)
in
let rec find_loop p1 p2 =
if (p1 == p2) then
p1
else
find_loop (List.tl p1) (List.tl p2)
in
match lst with
| [] -> []
| _ :: t ->
match find_an_elem lst t with
| [] -> []
| cirelem ->
let cirlen = find_circular_length cirelem in
let p = nth_tail cirlen lst in
find_loop lst p
;;

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

--
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
- Gene Spafford
Brian

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

```