removing cycles from cyclic/mutable list in ocaml?

Question

I'm not sure how to remove the cycles from a mutable list of type:

type 'a m_list = Nil | Cons of 'a * (('a m_list) ref)

E.g. if I had a list 3,2,2,1,2,1,2,1,..... I would want to get a 3,2,2,1.
What I can't figure out is the location of the initial cycling--I have a recursion that looks like this but I can't figure out how to wrap this into a recursive function; obviously here it would just checks the first few terms.

let remove list : unit =
  if is_cyclic list then match list with
    |Nil->()
    |Cons(_,v)-> match (!v) with
      |Nil->()
      |Cons(_,x)->match (!x) with
        |Nil->()
        |Cons(_,y)->match (!y) with
          |Nil->()
          |Cons(_,p) -> if is_cyclic (!p) then p:=Nil else ()

I have an is_cyclic function that tells me whether an m_list has a cycle or not. I'd like to do this either destructively (updating the reference) or indestructively (creating a new list).

Thanks!

score 3 · Answer 1 · edited May 23 '17 at 12:26

Based on Pascal Cuoq's answer to your previous question, you could try something like this:

let rec recurse list already_visited =
  match list with
    Nil -> ()
  | Cons(h, t) -> 
    if List.memq !t already_visited
    then t := Nil          
    else recurse !t (t :: already_visited)

let remove_cycles list = recurse list []

This traverses the list until it either reaches the end or visits an element twice. When the latter happens, it instead sets the last visited reference to Nil.

You may want to replace already_visited with another data structure if you have very large lists.

Niki Yoshiuchi · Answer 2 · 2011-04-01T18:33:36.627

If you don't have enough memory to store each previously visited element, you could instead using a cycle detection algorithm to find an element in the cycle, then using that, find the end of the cycle and overwrite it's next reference.

To do this, modify is_cyclic to return a 'a mlist ref instead of a bool. Assuming that it could possibly return an element in the middle of the cycle, run through the original list and check whether each element is in the cycle. This will give you the first element in the cycle.

From there it's easy to find the end of the cycle - just loop through the cycle until you get back to the beginning.

Something like this:

let rec in_cycle x st cyc =
if cyc == x then true
else
    match !cyc with Nil -> false
    | Cons(_, t) when t == st -> false
    | Cons(_, t) -> in_cycle x st t

let rec find_start l cyc =
    if in_cycle l cyc cyc then l
    else
        match !l with Nil -> raise Not_found
        | Cons(_, t) -> find_start t cyc

let rec find_end st cyc =
    match !cyc with Nil -> raise Not_found
    | Cons(_, t) ->
        if t == st then cyc
        else find_end st t

(* ... *)
let cyc = is_cyclic list in
let st = find_start list cyc in
let e = (find_end st cyc) in
match !e with Nil -> failwith "Error"
| Cons(v, _) -> e := Cons(v, ref Nil)

removing cycles from cyclic/mutable list in ocaml?

2 Answers2