Re: [Caml-list] Recursive lists

[Brian Hurt <bhurt@spnz.org>]

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