检查可变列表是否在ocaml中循环？

Question

我正在尝试编写一个函数来测试Ocaml中的可变列表是否包含一个循环(即,具有对自身的引用并连续重复).

我的清单定义为type 'a m_list = Nil | Cons of 'a * (('a m_list) ref).

到目前为止,我有:

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

但它不太正确,我不确定如何从这里开始...感谢您的帮助!

Answer 1

一旦两个 Cons 单元（在列表中的不同深度找到）相同，列表中就会出现一个循环。您的示例代码仅检查第一个 Cons 单元格是否再次出现在列表中。检查循环的一种方法是记住您在列表中访问过的所有 Cons 单元格，并将每个新单元格与所有先前的单元格进行比较。

我不会编写整个函数，但它可能如下所示：

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