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