检查可变列表是否在ocaml中循环? [英] checking whether mutable list has cycle in ocaml?

问题描述

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

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.

我的列表定义为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 ;;

但这不是很正确，我不确定如何从这里开始...感谢您的帮助！

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

推荐答案

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

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

这篇关于检查可变列表是否在ocaml中循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！