（注意：这篇文章是一个 literate-haskell 文件。您可以将其复制粘贴到文本缓冲区中，将其另存为someFile.lhs，然后使用 ghc 运行它。）

问题描述：我想创建一个具有相互引用的两种不同节点类型的图。下面的例子非常简化。两种数据类型 A和B在这里实际上是相同的，但是在原始程序中它们不同是有原因的。

我们会把无聊的东西扔掉。

数据类型定义本身很简单：

为了象征两者之间的差异，我们将给它们一个不同的 Show实例。

然后打结当然是微不足道的。

这导致：

这正是我想要的！

现在是棘手的部分。我想在运行时根据用户输入创建此图。这意味着我需要错误处理。让我们模拟一些（有效但无意义的）用户输入：

（用户当然不会直接输入这些列表；数据将首先被按摩到这个表格中）

在没有错误处理的情况下执行此操作很简单：

一旦Strings 的输入列表引用了在相应地图中找不到的内容，这显然会失败。“罪魁祸首”是fromJust；我们只是假设钥匙会在那里。现在，我可以确保用户输入实际上是有效的，并且只使用上面的版本。但这需要两次通过并且不会很优雅，不是吗？

所以我尝试Maybe在递归 do 绑定中使用 monad：

但这最终会无限循环：aMap需要bMap定义，bMap 需要aMap. 但是，在我开始访问任一映射中的键之前，需要对其进行全面评估，以便我们知道它是 aJust还是 a Nothing。我认为，对 in的调用maybe在makeMap'这里让我很头疼。它包含一个隐藏的case表达式，因此是一个可反驳的模式。

这同样适用，Either因此在这里使用一些ErrorT变压器对我们没有帮助。

我不想退回到运行时异常，因为那会让我回到IOmonad，那就是承认失败。

对上述工作示例的最小修改是仅删除 fromJust，并仅获取实际工作的结果。

这也不起作用，而且奇怪的是，导致行为略有不同！

使用调试器表明这些甚至不是无限循环（正如我所预料的那样），但执行只是停止了。我一无所获maps'，第二次尝试时，我至少可以进行第一次查找，然后停止。

我难住了。为了创建地图，我需要验证输入，但为了验证它，我需要创建地图！两个明显的答案是：间接和预验证。这两个都是实用的，如果有点不雅。我想知道是否可以在线进行错误捕获。

Haskell 的类型系统可以满足我的要求吗？fromJust（可能是这样，我只是不知道如何。）通过将异常渗透到顶层，然后将它们捕获，显然是可能的IO，但这不是我想要的方式。

编辑：U2Graph最初的问题是“与comonad 打结”，但这里真正有帮助的是与来自cirdec打结的二维结。原始问题（直到 Anwser）：

我想用来自comonad的数据打结

更丰富的数据结构

有一个功能

但是，当我尝试填写 for 时，我的大脑会遇到“发生检查” undefined：

我无法解决的问题是，我需要参考我正在构建的东西，它被深深地埋在了一个comonad中。我想确定圆圈实际上指向同一个重击。

解决它的最佳方法是什么？那是comonad要走U a的路吗？双向链表data T a = T (Maybe (T a)) a (Maybe (T a))似乎遇到了同样的问题，但将更难扩展到二维。

背景：我尝试在haskell中实现codegolf的老鼠赛跑。因此，由于计算耗时，我想通过 tying-the-know 引用相同的 thunk。

回答

解决方案来自Cirdec 的 Answer。它只是错过了我不想发表评论的一小步。

导致我的大脑遇到“发生检查”的原因是：要构建 aFullCell并在其领域打结，move我需要已经构建的U2Graph FullCell. 既然我已经说过了，这个要求很容易写成：

其中第一个参数是构造 my 的函数FullCell。Cirdec 的功能可以轻松调整。最后一步是将comonad带回来：

为什么不iterate定义为

在前奏曲中？

我正在尝试在 Haskell 中编写一个函数，该函数采用一个表格并根据该列中字符串的最大大小填充每列的单元格。我这样做的方法是使用技术 - 打结。这是我写的函数：

当我加载这个模块并尝试向函数 pipedTable 提供一些输入时，例如。

它给，

我不明白问题出在哪里。

tying-the-knot 策略可用于构建图，例如，使用简单的两条边图作为示例：

该策略相当优雅，但如果没有 Int 标签，我无法找到实际使用它的方法。例如，我如何编写一个函数来计算square值上的节点数量？

正如我在上一个问题中所解释的那样，如果您的节点上没有某种唯一标签，则不可能区分使用打结策略制作的两个图表。以双边图为例：

由于需要手动编写标签，以这种方式编写square有点不方便且容易出错。这种模式通常需要一个 monad：

但这也不能做到，因为单子是连续的。有什么方便的方法来写打结图吗？

我正在研究使用“打结”技术在 Haskell 中处理类似图形的事物。我想，循环列表只是一种无限列表内部实现，所以在理想世界中，人们不应该关心主题。但它会对计算复杂性产生显着影响，考虑以下示例，具有循环世界的一维元胞自动机：

这是一个只有两个单元的循环。让我们迈出一步：

很好，现在分两步：

这是 5 次调用而不是 4 次，这实际上意味着增加每一步的调用次数，所以我们在总步数上具有二次复杂度而不是线性。我可以使循环明确，如下所示：

但这很丑，虽然我真的对更复杂的结构感兴趣，比如图形。问题：有没有办法让这里的代码既好又快？还是希望编译器在某个光明的未来能够更好地处理上面的代码？

Ross Paterson：箭头和计算介绍了trace函数（第 11 页）：

该trace函数对于模块化循环程序中的魔术反馈步骤很有用。例如，考虑 Richard Bird 的著名repmin函数，它找到一棵树的最小叶值并创建一棵相同的树，每个叶值都被最小叶值替换，这两者都是通过巧妙地使用惰性求值和局部递归（如提供letrec）：

无论如何，我想知道如何trace在 JavaScript 中实现该函数，以便我们可以实现repmin如下：

为了实现trace，我们需要提供的本地递归，letrec以便我们可以编写如下内容：

我原本是想许下c诺言的。然而，这改变了trace. 那么，你能想出一种trace在 JavaScript 中实现而不改变其语义的方法吗？

我试图通过减少这个函数来绕过 Cont 和 callCC：

我设法达到了这一点：

在这一点上，我不知道如何处理递归定义f 什么是完成这种减少的最佳方法？

在编写具有本地类型推断功能的编程语言时（即，它能够推断除函数参数之外的类型，如 Scala），我遇到了循环依赖的问题。

我通过递归探索 AST 来执行类型检查/推理，并将每个可选类型节点延迟映射到类型检查节点。因为任何节点的类型可能取决于 AST 中其他节点的类型，所以我已经打好结这样我可以在推断/检查当前节点的类型时参考其他节点的类型（我保留键入的-AST 在 Reader monad 的环境中）。

这在典型情况下工作得很好，但会因循环依赖而崩溃，因为程序无休止地跟随循环寻找已知类型。

这类问题的解决方案一般（据我所知）是维护一个探索节点的集合，但我想不出在打结时这样做的参照透明方式，因为我事先不知道节点将被访问/评估的顺序，因为这取决于它们彼此之间的依赖关系图。

因此，我似乎需要维护一个本地的、可变的已探索节点集合。为此，我尝试了以下方法：

• 使用 State monad 失败了，因为似乎每个子计算都收到了自己的状态副本，因此无法在计算的不同分支之间共享有关已探索节点的信息。
• 将 IO monad 与 IORefs 一起使用，由于其严格性，这使我无法结缘。
• 与 IORefs 一起使用unsafePerformIO，这引入了突变发生无序或根本不发生的问题。
• 将 ST monad 与 STRefs 一起使用，这引入了与 IO monad 相同的严格问题。

最后，我想出了一个使用 ST monad 的解决方案，在该解决方案中，我在使用 AST 映射时强制进行惰性求值unsafeInterleaveST，这可行，但感觉很脆弱。

是否有更惯用和/或引用透明的解决方案，不是冗长或复杂的？我会包含一个代码示例，但我对这个问题最简单的表述是大约 250 行。