[Camllist] Recursive lists
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Brian Hurt <bhurt@s...> 
Subject:  Re: [Camllist] Recursive lists 
Sorry for the late reply. 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 (cnt1) (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, aweinspiring, entertaining, and a source of mindboggling amounts of excrement when you least expect it."  Gene Spafford Brian  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners