menghapus siklus dari daftar siklik/dapat diubah di ocaml?

Saya tidak yakin bagaimana cara menghapus siklus dari daftar tipe yang bisa diubah:

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

Misalnya. jika saya memiliki daftar 3,2,2,1,2,1,2,1,..... Saya ingin mendapatkan 3,2,2,1.
Yang tidak dapat saya pahami adalah lokasi perputaran awal--Saya memiliki rekursi yang terlihat seperti ini tetapi saya tidak tahu cara menggabungkannya menjadi fungsi rekursif; jelas di sini ini hanya akan memeriksa beberapa istilah pertama.

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

Saya memiliki fungsi is_cyclic yang memberi tahu saya apakah m_list memiliki siklus atau tidak. Saya ingin melakukan ini secara destruktif (memperbarui referensi) atau secara tidak merusak (membuat daftar baru).

Terima kasih!


mutable ocaml cyclic
person anon    schedule 01.04.2011    source sumber

Jawaban (2)


arrow_upward
3
arrow_downward

Berdasarkan jawaban Pascal Cuoq pada pertanyaan Anda sebelumnya pertanyaan, Anda dapat mencoba sesuatu seperti ini:

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 []

Ini melintasi daftar hingga mencapai akhir atau mengunjungi elemen dua kali. Jika hal terakhir terjadi, referensi yang terakhir dikunjungi akan disetel ke Nil.

Anda mungkin ingin mengganti already_visited dengan struktur data lain jika Anda memiliki daftar yang sangat besar.

person Victor Nicollet    schedule 01.04.2011

arrow_upward
2
arrow_downward

Jika Anda tidak memiliki cukup memori untuk menyimpan setiap elemen yang dikunjungi sebelumnya, Anda dapat menggunakan algoritme deteksi siklus untuk menemukan elemen dalam siklus, lalu menggunakannya, temukan akhir siklus dan timpa referensi berikutnya.

Untuk melakukannya, ubah is_cyclic untuk mengembalikan 'a mlist ref, bukan bool. Dengan asumsi bahwa ia mungkin dapat mengembalikan elemen di tengah siklus, jalankan daftar asli dan periksa apakah setiap elemen ada dalam siklus. Ini akan memberi Anda elemen pertama dalam siklus tersebut.

Dari sana, mudah untuk menemukan akhir siklus - cukup ulangi siklus tersebut hingga Anda kembali ke awal.

Sesuatu seperti ini:

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)
person Niki Yoshiuchi    schedule 01.04.2011