Are "open-ended list" and "difference-list" used in OCaml?

Question

Sometimes, I heard of open-ended list and difference-list. I know they are from prolog: Difference between "open-ended lists" and "difference lists"

But does OCaml use them?

I ask this question because in OCaml 99 problems, there is one problem:

Graph isomorphism. (medium)

Two graphs G1(N1,E1) and G2(N2,E2) are isomorphic if there is a bijection f: N1 → N2 such that for any nodes X,Y of N1, X and Y are adjacent if and only if f(X) and f(Y) are adjacent.

Write a function that determines whether two graphs are isomorphic. Hint: Use an open-ended list to represent the function f.

I even don't understand the hint:

Use an open-ended list to represent the function f

Questions:

1. Can anyone explain?
2. Or confirm we don't have such two things in OCaml?
3. If we don't have these two kinds of lists, how can we solve the problem above? Make all possible mappings between nodes in G1 and nodes in G2 and checking whether every pair adjacent?

Answer 1

Googling "open-ended list graph isomorphism" suggests that the question was copy-pasted as is from a set of Prolog exercises. The hint was present in the original version and of course made more sense in a Prolog context than in an OCaml one.

Here is a solution in Prolog to the graph isomorphism problem; it may use open-ended lists (I'm not familiar with the behavior of the standard library memberchk that does the work of checking or extending the isomorphism), but that's merely an implementation detail.

The general idea of the algorithm is to do backtracking on a structure representing a partial isomorphism, on which all the edges handled so far agree. You can implement that in any language, for example using a non-determinism monad, and I don't think tail-cell unification plays an important role here; using Map (persistent associative maps from the standard library) to manipulate the mapping from nodes of N1 to nodes of N2 would be just fine (and algorithmically much more efficient than linear search in an open-ended list).

The pseudo-code for the algorithm would be as follow:

let add_edge iso (n1,n2) (n1', n2') =
  if n1 is unbound in iso, extend it with n1->n1'
  same for (n2, n2')
  if n1 is bound to a node different from n1' return None
  same for (n2, n2')
  else Some iso

let graph_iso iso g1 g2 =
  if g1 is empty then Some iso
  else if has an edge e1 then
    for any e2 in g2 such that add_edge iso e1 e2 is Some iso'
      if graph_iso iso' (g1 - e1) (g2 - e2) is not None, return it
    else return None