удаление циклов из циклического/изменяемого списка в 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_cycle, которая сообщает мне, есть ли у m_list цикл или нет. Я хотел бы сделать это либо деструктивно (обновив ссылку), либо недеструктивно (создав новый список).

Спасибо!


mutable ocaml cyclic
person anon    schedule 01.04.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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