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

2つのConsセル（リストの異なる深さにあります）が同じになるとすぐに、リストにサイクルがあります。サンプルコードは、最初のConsセルがリストの下に再び表示されるかどうかのみをチェックします。サイクルをチェックする1つの方法は、リストを下に移動してアクセスしたすべての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の答えが最良ですが、逸話的な曖昧さのために、2つのカーソルを保持し、一方を他方の2倍の速度で進めることにより、一定のメモリでこのチェックを実行することもできます（ただし、計算コストは​​高くなります）。それらが等しくなるとすぐに停止します：

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 に答える