Если список длинный, вы можете использовать хеш-таблицу вместо списка для хранения посещенных ячеек и выполнения поиска в почти постоянное время.
Позвольте мне расширить и изменить код Паскаля:
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 определены следующим образом:
(* 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) ()