Using `=` on cyclic data structure causes out-of-memory error

Learning
1

Is this expected? The structural equality = can’t deal with cycles and causes a program to crash.

type t = { key : int; mutable prev : t option; mutable next : t option; }
let a = { key = 1; prev = None; next = None }
a.prev <- Some a
a.next <- Some a

utop # a = a;;
Out of memory during evaluation.
2

Yes. Structural comparison may not terminate on cyclic structures. It is documented as such in the manual if I’m not wrong.

Cheers,
Nicolas

1 Like
3

e1 = e2 tests for structural equality of e1 and e2. Mutable structures (e.g. references and arrays) are equal if and only if their current contents are structurally equal, even if the two mutable objects are not the same physical object. Equality between functional values raises Invalid_argument. Equality between cyclic data structures may not terminate. Left-associative operator, see Ocaml_operators for more information.

In this particular case I would have expected that = tests for physical equality using == first and would have found that a == a. In understand that in the general case avoiding infinite recursion in the case of cyclic structures is expensive and is not implemented likely for that reason.

4

Your intuition is correct, and holds true if you use compare instead of =. However, in the case of = (and <, <=, etc) this is not done so that one may have nan <> nan !

Cheers,
Nicolas

2 Likes