Проверка, есть ли в изменяемом списке цикл в ocaml?

Question

Я пытаюсь написать функцию, чтобы проверить, содержит ли изменяемый список в Ocaml цикл или нет (то есть имеет ссылку на себя и повторяется постоянно).

Мой список определяется как type 'a m_list = Nil | Cons of 'a * (('a m_list) ref),

Пока что у меня есть:

let is_cyclic list =
  let rec check xs = 
    match (!xs) with
     |Nil -> false
     |Cons(_,v) -> ((!v)==list)||check v in
  match list with
   |Nil -> false
   |Cons(_, x) -> check x ;;

но это не совсем правильно, и я не уверен, как действовать дальше... спасибо за любую помощь!

Answer 1

В списке есть цикл, как только две ячейки Cons (найденные на разных глубинах в списке) совпадают. Ваш пример кода только проверяет, появляется ли первая ячейка Cons снова внизу списка. Один из способов проверки циклов состоит в том, чтобы запомнить все ячейки "против", которые вы посетили в списке, и сравнить каждую новую ячейку со всеми предыдущими.

Я не собираюсь писать всю функцию, но это может выглядеть так:

let rec is_cyclic list already_visited =
  match list with
    Nil -> false
  | Cons(h, { contents = t }) -> 
    if List.memq list already_visited
    then (* list was traversed before *)
      ...
    else
      ...

Answer 2

Ответ Паскаля Куока является лучшим, но ради непонятной неизвестности вы также можете выполнить эту проверку с постоянной памятью (но с более высокими вычислительными затратами), удерживая два курсора и продвигая один из них в два раза быстрее, чем другой, и останавливаясь, как только они равны

let rec is_cyclic a b =    
  match a with 
    | Nil -> false 
    | Cons (_, { contents = a }) ->
      match b with 
        | Nil | Cons (_, { contents = Nil }) -> false
        | Cons (_, { contents = Cons (_, {contents = b}) } ->
          a == b || is_cyclic a b 

let is_cyclic l = is_cyclic l l  

Answer 3

Если список длинный, вы можете использовать хеш-таблицу вместо списка для хранения посещенных ячеек и выполнения поиска в почти постоянное время.

Позвольте мне расширить и изменить код Паскаля:

let rec is_cyclic list already_visited =
  match list with
    Nil -> false
  | Cons(h, { contents = t }) -> 
    V.mem already_visited h ||
    is_cyclic t (V.add already_visited h)

Модуль V поставляется из следующего функторного приложения:

module V = Visits.Make (struct type t = int end)

и посещения определяются следующим образом:

(* visits.ml *)
struct
  module Make (X : sig type t end) :
  sig
    type elt
    type t
    val create : int -> t
    val mem : t -> elt -> bool
    val add : t -> elt -> unit
  end with type elt = X.t =
  struct
    module H = Hashtbl.Make (
      struct
        type t = X.t
        let equal = ( == )
        let hash = Hashtbl.hash
      end
    )

    type elt = X.t
    type t = unit H.t
    let create len = H.create len
    let mem tbl x = H.mem tbl x
    let add tbl x = H.add tbl x ()
  end
end

Вышеприведенная реализация совершенно безопасна и ориентирована на будущее, но не полиморфна в отличие от решения на основе списка.

Можно написать полиморфную версию, которая использует печально известный модуль Obj, который нельзя использовать, не зная ряда вещей, которые официально не документированы. Использование Obj в приведенном ниже коде делает предположения о реализации модуля Hashtbl, который вряд ли сломается в будущем, но вас предупреждают.

Тем не менее, он полиморфен и поэтому прост в использовании:

(* visits.mli *)
type 'a t
val create : int -> 'a t
val mem : 'a t -> 'a -> bool
val add : 'a t -> 'a -> unit

(* visits.ml *)
module H = Hashtbl.Make (
  struct
    type t = Obj.t
        (* Warning: using Obj is not pure OCaml. It makes assumptions
           on the current implementation of Hashtbl,
           which is unlikely to change in incompatible ways
           anytime soon. *)

    let equal = ( == )
    let hash = Hashtbl.hash
  end
)

type 'a t = unit H.t
let create len = H.create len
let mem : 'a t -> 'a -> bool = fun tbl x -> H.mem tbl (Obj.repr x)
let add : 'a t -> 'a -> unit = fun tbl x -> H.add tbl (Obj.repr x) ()