智能纯功能套装

Question

由联合,交叉和差异组成的集合计算通常可以用许多不同的方式表达.是否有任何理论或具体实施试图最小化达到给定答案所需的计算量？

例如,我在尝试将无定形材料模拟中的原子分解为相邻壳时首先遇到了这种实际应用,其中第一个壳是某个给定原点原子的直接邻居,第二个壳是那些邻居的原子.第一个shell中的第一个shell不在第一个shell中,也不在第一个shell中:

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而不是最外层的shell.在实践中,需要构建大型中间组的解决方案较慢.

据推测,智能集实现可以构成要评估的表达式,然后在评估之前对其进行优化(例如,减小中间集的大小),以便提高性能.这样的集合实现是否存在？

Answer 1

你的问题立即让我想起了Haskell的流融合,在本文中有所描述.可以很容易地总结一般原则:您可以存储构建列表的方法,而不是存储列表.然后,列表转换函数直接在列表生成器上运行,这意味着所有操作融合到单个生成的数据中而没有任何中间结构.然后,当您完成组合操作时,您将运行生成器并生成数据.

所以我认为你的问题的答案是,如果你想要一些融合计算和消除中间数据结构的类似智能机制,你需要找到一种方法将一组转换为"共同结构"(这就是本文的论文)调用它)生成一个集合并直接对其进行操作,然后在完成后实际生成集合.

我认为这个概念背后有一个非常深刻的理论,该论文提示但从未说明,如果其他人知道它是什么,请告诉我,因为这与我正在做的其他事情非常相关!