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  

Answer 3

If the list is long, you may want to use a hash table instead of a list for storing the visited cells and performing the lookups in near-constant time.

Let me expand and modify Pascal's code:

let rec is_cyclic list already_visited =
  match list with
    Nil -> false
  | Cons(h, { contents = t }) -> 
    V.mem already_visited h ||
    is_cyclic t (V.add already_visited h)

The V module comes from the following functor application:

module V = Visits.Make (struct type t = int end)

and Visits is defined as follows:

(* visits.ml *)
struct
  module Make (X : sig type t end) :
  sig
    type elt
    type t
    val create : int -> t
    val mem : t -> elt -> bool
    val add : t -> elt -> unit
  end with type elt = X.t =
  struct
    module H = Hashtbl.Make (
      struct
        type t = X.t
        let equal = ( == )
        let hash = Hashtbl.hash
      end
    )

    type elt = X.t
    type t = unit H.t
    let create len = H.create len
    let mem tbl x = H.mem tbl x
    let add tbl x = H.add tbl x ()
  end
end

The implementation above is perfectly safe and future-proof but is not polymorphic unlike the list-based solution.

It is possible to write a polymorphic version that uses the infamous Obj module, which should not be used without knowing a number of things that are not officially documented. The use of Obj in the code below makes assumptions on the implementation of the Hashtbl module, which are unlikely to break in the future but you are being warned.

That said, it is polymorphic and therefore easy to use:

(* visits.mli *)
type 'a t
val create : int -> 'a t
val mem : 'a t -> 'a -> bool
val add : 'a t -> 'a -> unit

(* visits.ml *)
module H = Hashtbl.Make (
  struct
    type t = Obj.t
        (* Warning: using Obj is not pure OCaml. It makes assumptions
           on the current implementation of Hashtbl,
           which is unlikely to change in incompatible ways
           anytime soon. *)

    let equal = ( == )
    let hash = Hashtbl.hash
  end
)

type 'a t = unit H.t
let create len = H.create len
let mem : 'a t -> 'a -> bool = fun tbl x -> H.mem tbl (Obj.repr x)
let add : 'a t -> 'a -> unit = fun tbl x -> H.add tbl (Obj.repr x) ()