OCaml中使用"开放式列表"和"差异列表"吗？

Question

有时候,我听到的open-ended list和difference-list.我知道他们来自prolog:"开放式列表"和"差异列表"之间的区别

但是OCaml会使用它们吗？

我问这个问题是因为在OCaml 99问题中,有一个问题:

图同构.(介质)

如果存在双射f:N1→N2,则两个图G1(N1,E1)和G2(N2,E2)是同构的,使得对于任何节点X,当且仅当f(X)时,N1,X和Y的Y是相邻的)和f(Y)相邻.

编写一个函数,确定两个图是否同构.提示:使用开放式列表来表示函数f.

我甚至不理解提示:

使用开放式列表来表示函数f

问题:

1. 谁能解释一下？
2. 或者确认我们在OCaml中没有这两样东西？
3. 如果我们没有这两种清单,我们如何解决上述问题呢？在G1中的节点和G2中的节点之间进行所有可能的映射,并检查每对是否相邻？

Answer 1

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

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

该算法的总体思想是对表示部分同构的结构进行回溯，到目前为止处理的所有边都一致。你可以用任何语言来实现它，例如使用非确定性单子，我不认为尾部单元统一在这里发挥重要作用；使用（标准库中的持久关联映射）来操纵从节点到节点Map的映射就可以了（并且在算法上比开放式列表中的线性搜索更有效）。N1N2

该算法的伪代码如下：

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