Удалить циклы из циклического / изменяемого списка в 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

Основываясь на ответе Паскаля Куока на ваш предыдущий вопрос, вы можете попробовать что-то вроде этого:

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)