7

我正在尝试编写一个函数来测试 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 ;;

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

4

3 回答 3

3

只要两个 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
      ...
于 2011-03-29T05:51:44.537 回答
2

Pascal Cuoq 的答案是最好的，但为了避免轶事，您还可以通过保持两个游标并将其中一个游标的推进速度提高一倍，以恒定内存（但计算成本更高）执行此检查，并且一旦它们相等就停止：

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
于 2011-03-29T08:50:40.633 回答
0

如果列表很长，您可能希望使用哈希表而不是列表来存储访问过的单元格并在近乎恒定的时间内执行查找。

让我扩展和修改 Pascal 的代码：

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)

V 模块来自以下仿函数应用程序：

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

和访问定义如下：

(* 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

上面的实现是完全安全且面向未来的，但不像基于列表的解决方案那样是多态的。

可以编写一个使用臭名昭著的 Obj 模块的多态版本，如果不了解许多未正式记录的内容，则不应使用该模块。在下面的代码中使用 Obj 对 Hashtbl 模块的实现做出了假设，这些假设在未来不太可能中断，但您会被警告。

也就是说，它是多态的，因此易于使用：

(* 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) ()
于 2011-03-31T00:20:20.007 回答