问题标签 [tying-the-knot]

在阅读与 Haskell 相关的内容时，我有时会遇到“打结”的表达，我想我理解它的作用，但不知道如何。

那么，对这个概念有什么好的、基本的和简单易懂的解释吗？

更新：我添加了一个描述我最终解决方案的答案（提示：单一Expr数据类型是不够的）。

我正在为一种小表达式语言编写一个评估器，但我被困在这个LetRec结构上。

这是语言：

到目前为止，这是评估员：

这是我要评估的测试功能：

编辑：

根据 Travis 的回答和 Luke 的评论，我更新了我的代码以将 MonadFix 实例用于 Error monad。前面的示例现在可以正常工作了！但是，下面的示例无法正常工作：

评估时，评估器循环，没有任何反应。我猜我在这里做了一些过于严格的事情，但我不确定它是什么。我是否违反了 MonadFix 法律之一？

我想通过打结来写一段漂亮的代码（节省我很多时间来实现）。大致是这样的，

理论上，myinstr应该运行x以获得一个值，这将成为n. myinstr在Statemonad 中运行的 , 将n进入状态，但这不会影响x' 的计算。

我尝试过使用DoRec和幼稚的实现mfix，

但事情冻结了。是否有任何方法可以修复我的代码（或第一次正确设计它的方法）或者我应该写一些更直接的东西？

我正在用 Haskell 编写一个笨拙的解释器，我想出了我认为对程序非常有趣的描述：

然而，将一个 Brainfuck 程序的文本表示解析为这种数据类型是很棘手的。尝试正确解析方括号会出现问题，因为有一些打结要做，以便Instruction循环内的最终链接再次链接到循环Control。

更多初步信息。有关所有详细信息，请参阅github repo 上的此版本。

这是我尝试过的：

我想我可以以某种方式使用延续来将信息从'['案例传递到']'案例，反之亦然，但我对 Cont 没有足够的把握，除了对看起来可能有效的事情进行疯狂猜测之外，我还没有真正做任何事情，如上所示push和pop。这编译并运行，但结果是垃圾。

这种情况可以Cont用来打结吗？如果不是，那么我应该使用什么技术来实现toProgram？

注 1：我之前有一个微妙的逻辑错误：loopControl = branch is0布尔值反转了。

注意 2：我设法使用MonadFix（如 jberryman 建议的那样）State提出了一个解决方案（请参阅github 存储库的当前状态）。我仍然想知道如何做到这一点Cont。

注 3：我的 Racketeer 导师为我准备了一个类似的 Racket 程序（查看所有修订版）。他的管道/管道输出技术可以使用 翻译成 HaskellCont吗？

tl; 博士我设法使用 MonadFix 做到了这一点，而其他人则设法使用 Racket 的延续组合器做到了这一点。我很确定这可以Cont在 Haskell 中完成。你能告诉我怎么做吗？

假设我有一个像这样的愚蠢的小案例类：

我怎样才能定义a和b不可变的那样a.otherisb和b.otheris a？scala 是否提供了一些“打结”的方法？我想做这样的事情：

可能性

在 Haskell 中，我会这样做：

a与和的绑定b包含在同一个let表达式中，或者在顶层。

或者，在不滥用 Haskell 的自动 letrec 功能的情况下：

注意惰性模式，~(a', b')这很重要。

我正在处理一个涉及打结的 Haskell 项目：我正在解析图形的序列化表示，其中每个节点都位于文件的某个偏移量处，并且可能通过其偏移量引用另一个节点。do rec所以我需要在解析时建立一个从偏移量到节点的映射，我可以在一个块中反馈给自己。

我有这个工作，并且有点合理地抽象成一个StateT-esque monad 转换器：

该tie函数是魔法发生的地方：调用runRecStateT产生一个值和一个状态，我将其作为它自己的未来提供。请注意，它get允许您读取过去和未来的状态，但put只允许您修改“现在”。

问题 1：一般来说，这似乎是实现这种打结模式的一种不错的方式吗？或者更好的是，是否有人对此实施了通用解决方案，而我在窥探 Hackage 时忽略了这一点？我用头撞了一下Contmonad，因为它看起来可能更优雅（参见Dan Burton的类似帖子），但我就是无法解决。

完全主观的问题 2：我对我的调用代码最终看起来的方式并不完全兴奋：

显然，这里省略了实现细节，重要的一点是我必须在 let 绑定past中获取和future状态，模式匹配它们（或显式使先前的模式变得惰性）以提取我关心的任何内容，然后构建我的节点，更新我的状态，最后返回节点。似乎不必要地冗长，而且我特别不喜欢意外地使提取and状态的模式变得严格是多么容易。那么，有人能想到更好的界面吗？pastfuture

我偶然发现了一些我猜是 中的错误Data.Map，但这也很可能是我的 Haskell 知识中的错误。希望有人能澄清它是什么:)

请参考这个要点。我正在将循环链表结构序列化为字节流。对于任何给定的节点，形式为：

我希望它被序列化为一对字节：第一个字节表示val，第二个字节表示字节流中next可以定位的偏移量。例如，我期望：

被序列化为[0, 1, 1, 0]. 没什么大不了的。

这里稍微棘手的部分是我正在利用该MonadFix实例RWST来“打结”字节流偏移量：我维护一个从节点到偏移量的映射，在序列化期间填充映射，但也引用映射中不存在的条目在序列化完成之前必然存在。

当地图实现是Data.HashMap.Lazy（来自unordered-containers）时，这很有效。但是，当实现是通常的Data.Map（来自容器）时，程序堆栈溢出 - 没有双关语 -Map无限尝试使用(==).

所以我的问题是：这是一个错误Data.Map，还是我对这些结构在存在mfix缺陷的情况下应该如何表现的假设？

我有一个问题，我不知道如何推理。我正要问是否有人可以帮助我解决具体问题，但我突然意识到我可以问一个更笼统的问题，并希望因此得到更好的总体理解。希望。所以这里是：

当您的程序太懒惰时，这通常很明显，因为您最终会遇到诸如空间泄漏之类的明显问题。我有相反的问题：我的程序太严格了。我正在尝试打结 ，并发现我尝试做的某些事情会以某种方式击败我需要的懒惰。所以我的一般问题是，如何调试不需要的严格性？

为了完整起见，这是我的具体情况：我在 中RWS，编写器组件填充地图，阅读器组件观察该地图的最终状态。在完成填充之前，我不能对这张地图做任何严格的事情。在地图中查找值似乎没有问题，例如：

但是(!)使用失败error，我宁愿使用我的 monad 失败fail。所以我想做如下的事情：

这导致我的程序<<loop>>，我不明白。在我看来，这似乎不应该比 using 更严格(!)，但显然我错了......

在我最初尝试创建一个不相交的集合数据结构时，我创建了一个Point带有parent指向另一个指针的数据类型Point：

为了创建一个单例集，创建了一个以Point自身为父集的 a （我相信这被称为打结）：

现在，当我想写findSet（即跟随父指针，直到找到Point它的父对象本身）时，我遇到了一个问题：是否可以检查是否是这种情况？一个幼稚Eq的实例当然会无限循环——但这个检查在概念上是否可以编写？

（我最终使用 aMaybe Point作为父字段，请参阅我的另一个问题。）

几年前，我参加了一门算法课程，其中我们给出了以下问题（或类似问题）：

有一栋n带电梯的楼层，一次只能上2层，一次只能下3层。使用动态编程编写一个函数，该函数将计算电梯从一层i到另一层所需的步数j。

这显然很容易使用有状态的方法，您创建一个长度为 n 个元素的数组并用值填充它。您甚至可以使用一种技术上的无状态方法，该方法涉及将结果累积为递归传递。我的问题是如何通过使用惰性评估和打结以无状态的方式做到这一点。

我想我已经设计了正确的数学公式：

wherei+2和i-3在允许的值范围内。

不幸的是，我无法让它终止。如果我i+2先放置案例，然后选择一个偶数层，我可以让它评估低于目标水平的偶数层，但仅此而已。我怀疑它会直接射到最高的楼层，下降 3 层，然后重复，永远在最高的几层之间摇摆。

所以它可能是以深度优先的方式探索无限空间（或有限但有循环）。如果不使用大量有效模仿有状态方法的数据结构，我想不出如何以广度优先的方式探索空间。

虽然这个简单的问题令人失望地困难，但我怀疑已经看到了一维的解决方案，我可能能够使其适用于问题的二维变化。

编辑：很多答案试图以不同的方式解决问题。这个问题本身对我来说并不有趣，问题是关于使用的方法。Chaosmatter 创建一个minimal可以比较潜在无限数的函数的方法可能是朝着正确方向迈出的一步。不幸的是，如果我尝试创建一个表示具有 100 层楼的建筑物的列表，则计算结果需要很长时间，因为子问题的解决方案没有被重用。

我尝试使用自引用数据结构，但它没有终止，存在某种无限循环。我将发布我的代码，以便您了解我的目标。如果有人实际上可以在自引用数据结构上使用动态编程解决问题，我会更改已接受的答案，以避免计算不止一次。

您可以看到如何1 + levels !! i尝试引用先前计算的结果以及如何filter (\n -> n >= 0 && n <= 10) [x+2,x-3]尝试将值限制i为有效值。正如我所说，这实际上不起作用，它只是演示了我希望解决此问题的方法。解决它的其他方法对我来说并不有趣。