從ocaml中的循環/可變列表中刪除循環？

Question

我不知道如何從類型的可變列表中刪除循環：

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是否有循環。我希望以破壞性的方式（更新參考文獻）或堅持不懈地（創建新列表）來做到這一點。

謝謝！

Answer 1

基於Pascal Cuoq's answer你剛纔的問題，你可以嘗試這樣的事：

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如果你有非常大的列表。

Answer 2

如果你沒有足夠的內存來存儲每個以前訪問過的元素，可以轉而使用週期檢測算法來找到在週期的元素，然後使用，找到週期結束並覆蓋它的下一個參考。

爲此，請修改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)