ลบวงจรออกจากรายการ cyclic / ที่ไม่แน่นอนใน ocaml หรือไม่

ฉันไม่แน่ใจว่าจะลบวงจรออกจากรายการประเภทที่ไม่แน่นอนได้อย่างไร:

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

ฉันมีฟังก์ชัน is_cyclic ที่บอกฉันว่า m_list มีวงจรหรือไม่ ฉันต้องการทำสิ่งนี้แบบทำลายล้าง (อัปเดตข้อมูลอ้างอิง) หรือไม่ทำลายล้าง (สร้างรายการใหม่)

ขอบคุณ!


mutable ocaml cyclic
person anon    schedule 01.04.2011    source แหล่งที่มา

คำตอบ (2)


arrow_upward
3
arrow_downward

อิงตามคำตอบของ 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 []

วิธีนี้จะลัดเลาะไปตามรายการจนกว่าจะถึงจุดสิ้นสุดหรือไปที่องค์ประกอบสองครั้ง เมื่อเกิดเหตุการณ์หลังขึ้น ระบบจะตั้งค่าการอ้างอิงที่เข้าชมครั้งล่าสุดเป็น Nil แทน

คุณอาจต้องการแทนที่ already_visited ด้วยโครงสร้างข้อมูลอื่นหากคุณมีรายการจำนวนมาก

person Victor Nicollet    schedule 01.04.2011

arrow_upward
2
arrow_downward

หากคุณมีหน่วยความจำไม่เพียงพอที่จะจัดเก็บแต่ละองค์ประกอบที่เยี่ยมชมก่อนหน้านี้ คุณสามารถใช้อัลกอริธึมการตรวจจับรอบเพื่อค้นหาองค์ประกอบในรอบนั้นแทน จากนั้นใช้สิ่งนั้น ค้นหาจุดสิ้นสุดของรอบและเขียนทับการอ้างอิงถัดไป

เมื่อต้องการทำเช่นนี้ ให้แก้ไข is_cyclic เพื่อส่งคืน 'a mlist ref แทนที่จะเป็น bool สมมติว่าอาจส่งคืนองค์ประกอบที่อยู่ตรงกลางของวงจร ให้ดำเนินการผ่านรายการเดิมและตรวจสอบว่าแต่ละองค์ประกอบอยู่ในวงจรหรือไม่ นี่จะทำให้คุณมีองค์ประกอบแรกในรอบนี้

จากนั้นจะพบจุดสิ้นสุดของวงจรได้ง่าย เพียงวนซ้ำจนกว่าคุณจะกลับมาที่จุดเริ่มต้น

บางสิ่งเช่นนี้:

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