haskell - 图构建期间的连续传递风格 (CPS)

Question

我正在开发一个用于分割曲面的库。为了表示网格拓扑，我使用了一种 split 顶点板条数据结构(参见左侧的图表)。



在构建网格的过程中，也可以将其视为图形，它创建的节点应该指向另一个尚不存在的节点(请参见右侧的图表 - 虚线箭头表示 future 的链接)。经典的解决方案是创建一个带有空指针的节点，然后在创建另一个节点时更新它。由于我正在研究 Haskell :) 并且我不想进入代码的阴暗面(杂质)，我想知道是否可以在不更新数据的情况下构建网格(图形)。我想 CPS(Continuation Passing Style)可以完成这项工作，但我想不出办法。

难道只是个梦？

更新

让我稍微澄清一下我的问题。我正在寻找一种方法来创建具有直接链接(指针)的节点，通过直接链接，我的意思是没有中间表或映射。只是一个简单的数据定义:

data Mesh = Edge Vertex Mesh Mesh Vertex | Ground

如果我没有弄错并且如果可行，CPS 将允许高效创建(无需节点更新)和高效横向(无需在 map 上查找)图形。另一方面，图将变得完全不可变，即单个更改需要通过整个图传播，例如改变列表的尾部。

我错了吗？如果没有，怎么办？

Answer 1

您需要的是一种称为 tying the knot 的技术。 .它利用惰性评估来完成工作。不需要 CPS。

假设您可以通过某个唯一 ID(字符串、整数或其他)来标识每个节点。还假设当您创建一个节点时，您已经知道它指向的所有节点的 ID，无论它们是否已经创建。然后你可以使用这个技术。

你串了一个 nodes :: Data.Map NodeID Node通过你的图形创建函数(为了额外的方便，使用状态 monad)。创建节点时，将其添加到 map 中。当您创建一条应指向名为 x 的节点的边时，您使用的是 fromMaybe $ lookup nodes x .名为 x 的节点是否已经创建或将在将来创建都无关紧要。只要它是在某个时候创建​​的，您就设置好了。它只会在您需要时从 map 中获取。

这就是我过去从文本描述创建图表的方式。也许还有其他更好的方法。

如果在创建节点时，您不知道节点将指向的所有节点的 ID，则需要稍微修改此技术，例如将 map 从节点 ID 传递到其邻居列表，并逐步构建每个列表。

在完成图形构建之前，您应该小心并避免评估惰性值。