问题标签 [zipper]

问题很简单：我无法理解Zipper数据结构。

我的问题与它与树的使用有关。

我想了解如何使用 zipper 更改树节点。以及如何不复制整个树（或大部分）。

请澄清我是否对拉链有误。也许它无法帮助更新树？
或者，也许，可以更新树而我只是看不到路？

所以我一直在阅读一些关于 Haskell（以及其他函数式语言，我想）中的 Zipper 模式来遍历和修改数据结构的内容，我认为这对我来说是一个磨练创建类型技能的好机会Haskell 中的类，因为该类可以提供一个通用的遍历接口供我编写代码，而与遍历的数据结构无关。

我想我可能需要两个类——一个用于根数据结构，一个用于为遍历第一个而创建的特殊数据结构：

但是当我用一些简单的数据结构（如列表）尝试这些时：

或者二叉树：

我无法编译它，我的每个Zippable实例定义都会出现很多这样的错误：

所以我不确定从这里去哪里。我怀疑我的问题是我试图将这两个实例绑定在一起，而(Zipper z) =>声明只是想z成为 any Zipper。

假设我们有一些这样的 XML：

现在，查看 zip_filter/xml.clj 中的示例，我已经知道如何获取我感兴趣的单个值。

我想知道如何做一些事情，比如返回 (ce) 的文本值对列表。

编辑：

这是一些工作代码，但它非常难看。不要求进行微不足道的重构，但是拉链给我们提供了更好的方法来做到这一点吗？

我认为拉链是个好主意；它优雅地提供了一种遍历列表或树的方法，并以一种功能性的方式进行本地更新。

渐近地，成本似乎是合理的。但是遍历数据结构需要在每次迭代时分配内存，而普通的列表或树遍历只是指针追逐。这似乎很昂贵（如果我错了，请纠正我）。

成本是否高得令人望而却步？什么情况下使用拉链是合理的？

假设我想更改orange node以下树中的。

因此，我需要做的唯一其他更改是left pointer在green node.

将blue node保持不变。

我在某个地方错了吗？因为根据这篇文章（解释zippers），即使是蓝色节点也需要更改。

同样，在同一篇文章的这张图片（重新着色）中，为什么我们要更改橙色节点（当我们更改节点时x）？

我有一棵树表示为嵌套向量。我想indexed对树进行概括，像这样显示每个节点的索引，

天真的实现会直接使用 clojure.zip （正如这里已经问过的）

但是 recurring withclojure.zip/next会执行前序遍历，在这种情况下会导致无限循环（未访问的节点被无限地conj编入[:found]向量中）。另一种方法是使用clojure.walk/postwalk，但它不提供结构信息，例如索引。

你将如何实现这一点？是否有一个postorder-nextfor zip 可以立即解决它？

当一个人想要遍历一棵树并保持当前位置时，Zipper 数据结构很棒，但是如果他们想要跟踪一个以上的位置，应该使用什么数据结构呢？

让我用例子来解释：

• #haskell 频道上有人告诉我，yi 编辑器中使用拉链来表示光标位置。这很好，但是如果你想有两个游标怎么办。就像如果你想代表一个选择，你需要知道选择的开始和结束。
• 在 wikibooks 上的 Minotaur 示例中，他们使用 Zipper 来表示 Minotaur 在迷宫中的位置。如果我想将敌人添加到迷宫中，用拉链代表他们的位置同样有意义。
• 最后一个实际上是从我的迷你项目开始的：作为学习 Haskell 的一部分，我正在尝试使用 cairo 和 gth2hs 可视化树结构。到目前为止一切顺利，但现在我想选择一个或多个节点并能够例如移动它们。因为可以有超过一个选定的节点，所以我不能只使用教科书中定义的 Zipper。

有一个简单的（天真的？）解决方案，类似于他们在 XMonad 的早期版本中使用的解决方案，其中涉及有限映射，如此处所述。

也就是说，例如在我的示例项目中，我会将选定的节点存储在索引映射中，并用索引替换它们在主结构中的表示。但是这种解决方案有很多缺点。就像上面链接中解释的那样，或者说，在我的示例中，取消选择所有节点将需要搜索整个树。

假设我有以下两个case classes：

和以下Person类实例：

现在，如果我想更新zipCode的raj话，我将不得不这样做：

随着更多级别的嵌套，这变得更加丑陋。有没有更简洁的方法（比如 Clojure 的update-in）来更新这样的嵌套结构？

我正在为遗传编程问题创建 s 表达式树，并且需要在进化过程中更改部分树。我遇到了Clojure 拉链功能，它看起来应该是完美的，但对于我的生活，我无法弄清楚如何使用它。

例如，假设我创建了一个拉链

我理解这表示以 + 为根的树，它看起来像这样：

但是，我的拉链不同意这一点：如果我要求第一个节点，(-> zipped zip/down zip/node)它会给我+（这是正确的），但它(-> zipped zip/down zip/down)不会带我去-，而是返回nil. 确实，(-> zipped zip/down zip/rights)将树的其余部分作为根右侧的兄弟姐妹，这表明我根本没有树：

我很确定我正确地表示了我的树，因为当我执行它们时，我得到了正确的答案。拉链是否期望不同的布局？

我正在尝试从我自己的地图创建一个拉链。根据拉链定义，

参数分支？孩子们很清楚，我能够定义它。但是 make-node 功能令人困惑。我给出了一个我认为没有被使用的实现。

我有一张地图

我想从这张地图上做一个拉链。所以我使用了以下拉链函数调用，

这工作正常。即使给 make-node 参数 nil，它也可以工作。我不明白何时何地将使用此参数。