ocaml - 检查可变列表在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
      ...