ocaml - OCaml 中是否使用了 "open-ended list"和 "difference-list"？

Question

有时，我听说 open-ended list和 difference-list .我知道它们来自序言:Difference between "open-ended lists" and "difference lists"

但是 OCaml 使用它们吗？

我问这个问题是因为在 OCaml 99 problems ，有一个问题:

图同构。 (中等的)

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.

我什至不明白提示:

Use an open-ended list to represent the function f

问题:

谁能解释一下？

或者确认我们在 OCaml 中没有这两件事？

如果我们没有这两种列表，如何解决上面的问题呢？在 G1 中的节点和 G2 中的节点之间进行所有可能的映射，并检查每对是否相邻？

Answer 1

谷歌搜索“开放式列表图同构”表明该问题是从一组 Prolog 练习中复制粘贴的。这个提示出现在原始版本中，当然在 Prolog 上下文中比在 OCaml 上下文中更有意义。

这是a solution in Prolog图同构问题；它可能使用开放式列表(我不熟悉执行检查或扩展同构工作的标准库 memberchk 的行为)，但这只是一个实现细节。

该算法的一般思想是对表示部分同构的结构进行回溯，到目前为止处理的所有边都同意。您可以用任何语言实现它，例如使用非确定性 monad，我认为尾单元统一在这里没有重要作用；使用 Map (来自标准库的持久关联映射)操作来自 N1 节点的映射。到 N2 的节点会很好(并且在算法上比开放式列表中的线性搜索更有效)。

该算法的伪代码如下:

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