Re: [Caml-list] Cyclic data structures: internal representation

[Dmitry Grebeniuk <gdsfh1@gmail.com>]

Hello.

> - is there any easy way to check if a list is cyclic or not? The only way I see is to go down the list, checking at every step if this particular sublist has already been seen. But it's rather heavy.

> - the documentation on the = sign (http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html) mentions that "Equality between cyclic data structures may not terminate." It seems to terminate if one or the other of the data structures is not cyclic. Does it ever terminate when both data sstructures are cyclic, or does it always loop?

  Both these questions are solved with my library ocaml-cyclist:
https://forge.ocamlcore.org/projects/ocaml-cyclist/
  I don't remember exact details, but generally I use
"tortoise and hare" algorithm.

  Also note that lists with a cycle can also contain some prefix
that doesn't appear in the cycle (it happens when list with cycle
is appended to "linear" list).  That's also covered by ocaml-cyclist:

        value length : list 'a -> (int * int);
        (** Returns [(prefix_len, cycle_len)] of the argument.
            (0, 0) for empty list, (n, 0) for linear list,
            (0, n) for circular list, (n, m) for generic-shaped
            cyclic list.  (n, m > 0)
        *)

  As for equality, you can use

        value for_all2 : ?strict:bool ->
          ('a -> 'b -> bool) -> list 'a -> list 'b -> bool;

to write the code like

    let list_eq a b = Cyclist.for_all2 ~strict:true ( = ) a b

which will run correctly.  However, the following lists will be
considered equal: [{1; 2; 3}] and [1; 2; {3; 1; 2; 3; 1; 2}] (curly braces
denote the cycle of list; it's for illustration purposes only).
  Using other library functions you can strenghten your equality
relation.