集合算法的 Ocaml 实现建议

Question

我在 ocaml 中转换以下算法时遇到问题 为了实现这个算法，我使用了 Set.Make(String) 函子，实际上输入和输出是 2 个函数 任何人都可以在 ocaml 中为我提供精确的代码帮助，以便执行

以下操作实际上是实时变量算法[PDF] ..非常感谢您的帮助

for all n, in[n] = out[n] = Ø
w = { set of all nodes }
repeat until w empty
    n = w.pop( )
    out[n] = ∪  n’ ∈ succ [n] in[n’]
    in[n] = use[n] ∪ (out[n] — def [n])
    if change to in[n],
        for all predecessors m of n, w.push(m)
end

Answer 1

for all n, in[n] = out[n] = Ø
    w = { set of all nodes }
    repeat until w empty
    n = w.pop( )
    out[n] = ∪  n’ ∈ succ [n] in[n’]
    in[n] = use[n] ∪ (out[n] — def [n])
    if change to in[n],
    for all predecessors m of n, w.push(m)
end

我很难说出这里究竟发生了什么。我认为您的文本存在一些对齐问题 --repeat Until wempty 应该重复接下来的 5 行，对吧？ in 和 out 函数如何，对我来说它们看起来像数组？除了这些缺陷之外，我还将解决一些我遵循的一般规则。

我必须将 C 和 Fortran 算法中的许多数值方法翻译成函数式语言，我给你一些建议。

0) 定义所使用的数据类型。这将真正帮助您进行下一步（剧透：寻找功能结构）。一旦了解了数据类型，您就可以更准确地定义最终将应用的函数结构。

1）寻找功能性结构。折叠、递归和映射，以及何时使用它们。例如，所有前辈 m 的 是一个折叠（不确定它是否会折叠在树或列表上，但仍然是一个折叠）。 While 循环是递归的好地方——但不必担心使其成为尾调用，您可以稍后修改参数以遵守这些要求。不用担心是否 100% 纯净。删除足够多的不纯结构（引用或数组），以功能性的方式感受算法。

2) 尽可能地编写算法的任何部分。将函数留空，添加虚拟值，然后只实现你所知道的——然后你就可以提出更好、更明智的问题。

3）重写它。您很可能错过了一些函数构造或使用了数组或引用，现在您意识到可以使用列表或集合或通过传递累加器。您可能已经定义了一个列表，但后来您意识到您无法随机访问它（好吧，这将非常有害），或者需要前后遍历它（对于拉链来说是一个好地方）。不管怎样，当你最终得到它时你就会知道，你的脸上应该露出灿烂的笑容。