2

タイプの可変リストからサイクルを削除する方法がわかりません。

type 'a m_list = Nil | Cons of 'a * (('a m_list) ref)

たとえば、リスト3,2,2,1,2,1,2,1、.....がある場合、3,2,2,1を取得したいと思います。
私が理解できないのは、最初のサイクリングの場所です。このような再帰がありますが、これを再帰関数にラップする方法がわかりません。明らかにここでは、最初のいくつかの用語をチェックするだけです。

let remove list : unit =
  if is_cyclic list then match list with
    |Nil->()
    |Cons(_,v)-> match (!v) with
      |Nil->()
      |Cons(_,x)->match (!x) with
        |Nil->()
        |Cons(_,y)->match (!y) with
          |Nil->()
          |Cons(_,p) -> if is_cyclic (!p) then p:=Nil else ()

m_listにサイクルがあるかどうかを通知するis_cyclic関数があります。これを破壊的に（参照を更新する）または破壊的に（新しいリストを作成する）のいずれかで実行したいと思います。

ありがとう！

4

2 に答える 2

3

前の質問に対する Pascal Cuoq の回答に基づいて、次のようなことを試すことができます。

let rec recurse list already_visited =
  match list with
    Nil -> ()
  | Cons(h, t) -> 
    if List.memq !t already_visited
    then t := Nil          
    else recurse !t (t :: already_visited)

let remove_cycles list = recurse list []

これは、最後に到達するか、要素に 2 回アクセスするまで、リストをトラバースします。後者が発生すると、代わりに最後にアクセスした参照が に設定されNilます。

already_visitedリストが非常に大きい場合は、別のデータ構造に置き換えることができます。

于 2011-04-01T17:12:16.540 に答える
2

以前にアクセスした各要素を格納するのに十分なメモリがない場合は、代わりにサイクル検出アルゴリズムを使用してサイクル内の要素を見つけ、それを使用してサイクルの終わりを見つけ、次の参照を上書きすることができます。

これを行うには、 の代わりにis_cyclicを返すように変更します。サイクルの途中で要素を返す可能性があると仮定して、元のリストを実行し、各要素がサイクル内にあるかどうかを確認します。これにより、サイクルの最初の要素が得られます。'a mlist refbool

そこから、サイクルの終わりを見つけるのは簡単です。最初に戻るまで、サイクルをループするだけです。

このようなもの：

let rec in_cycle x st cyc =
if cyc == x then true
else
    match !cyc with Nil -> false
    | Cons(_, t) when t == st -> false
    | Cons(_, t) -> in_cycle x st t

let rec find_start l cyc =
    if in_cycle l cyc cyc then l
    else
        match !l with Nil -> raise Not_found
        | Cons(_, t) -> find_start t cyc

let rec find_end st cyc =
    match !cyc with Nil -> raise Not_found
    | Cons(_, t) ->
        if t == st then cyc
        else find_end st t

(* ... *)
let cyc = is_cyclic list in
let st = find_start list cyc in
let e = (find_end st cyc) in
match !e with Nil -> failwith "Error"
| Cons(v, _) -> e := Cons(v, ref Nil)
于 2011-04-01T18:24:10.333 に答える