checking whether mutable list has cycle in ocaml?

Question

I'm trying to write a function to test whether a mutable list in Ocaml contains a cycle or not (that is, has a reference to itself and repeats continuously.

My list is defined as type 'a m_list = Nil | Cons of 'a * (('a m_list) ref).

So far, I have:

let is_cyclic list =
  let rec check xs = 
    match (!xs) with
     |Nil -> false
     |Cons(_,v) -> ((!v)==list)||check v in
  match list with
   |Nil -> false
   |Cons(_, x) -> check x ;;

but it's not quite right and I'm unsure how to proceed from here...thanks for any help!

Answer 1

There is a cycle in the list as soon as two Cons cells (found at different depths in the list) are the same. Your example code only checks if the first Cons cell appears again down in the list. One way to check for cycles is to remember all the Cons cells you have visited going down the list, and to compare each new cell to all the previous ones.

I'm not going to write the entire function, but it may look like this:

let rec is_cyclic list already_visited =
  match list with
    Nil -> false
  | Cons(h, { contents = t }) -> 
    if List.memq list already_visited
    then (* list was traversed before *)
      ...
    else
      ...

Answer 2

Pascal Cuoq's answer is the best one, but for the sake of anecdotal obscurity, you can also perform this check with constant memory (but at a higher computational cost) by keeping two cursors and advancing one of them twice as fast as the other, and stopping as soon as they are equal:

let rec is_cyclic a b =    
  match a with 
    | Nil -> false 
    | Cons (_, { contents = a }) ->
      match b with 
        | Nil | Cons (_, { contents = Nil }) -> false
        | Cons (_, { contents = Cons (_, {contents = b}) } ->
          a == b || is_cyclic a b 

let is_cyclic l = is_cyclic l l