智能纯函数集

Question

由并集、交集和差集组成的集合计算通常可以用许多不同的方式来表示。是否有任何理论或具体实现可以尝试最小化得出给定答案所需的计算量？

例如，当我试图将非晶态材料的模拟中的原子分解成相邻的壳层时，我第一次遇到了这个实际应用，其中第一个壳层是某个给定原始原子的直接邻居，第二个壳层是那些与第一个壳层相邻的原子，这些原子既不在第一个壳层中，也不在第一个壳层之前的原子中：

nth 0 = singleton i
nth 1 = neighbors i
nth n = reduce union (map neighbors (nth(n-1))) - nth(n-1) - nth(n-2)

有许多不同的方法来解决这个问题。您可以在组成结果的同时增量地测试每个集合中的成员资格，也可以计算三个相邻shell的并集，并使用交集删除前两个shell，只留下最外层的一个。在实践中，需要构造大型中间集的解决方案速度较慢。

是否存在这样的set实现？

Answer 1

您的问题立即让我想起了this paper中描述的Haskell的流融合。一般原则很容易总结:不是存储列表，而是存储一种构建列表的方法。然后，当您完成组合操作时，您可以运行生成器并生成数据。

所以我认为你的问题的答案是，如果你想要某种类似的智能机制来融合计算并消除中间数据结构，你需要找到一种方法来将集合转换为“共结构”(论文称之为“共结构”)，生成集合并直接对其进行操作，然后在完成操作后实际生成集合。

我认为这篇论文暗示的这个概念背后有一个非常深刻的理论，但没有详细说明，如果这里有人知道它是什么，请让我知道，因为这与我正在做的其他事情也非常相关！