haskell - 带镜头和 zipper 的遍历树

Question

我正在学习镜头包。我必须说这是一项相当具有挑战性的任务。

有人能告诉我如何用镜头的 zipper 穿过一棵树吗？特别是，我如何编写一个函数来获取根列表并允许我访问子树的分支？

假设我有这棵树。如果我的输入是 [1, 3] ，该功能应该允许我访问节点 10 和 11。

import Control.Lens
import Data.Tree
import Data.Tree.Lens

testTree = Node 1 [ Node 2 [ Node 4 [ Node 6 [], Node 8 [] ],
                             Node 5 [ Node 7 [], Node 9 [] ] ],
                    Node 3 [ Node 10 [], 
                             Node 11 [] ] 
                  ]

zipperTree = zipper testTree

另外， saveTape具体怎么用？和 restoreTape保存遍历路径(到 StateT 或 IORef)？

Answer 1

编辑:我通常在 ghci 中进行实验以理解新代码，所以对于像我这样的人，我创建了一个 School of Haskell post/page以下示例附带，但它们是可编辑和可运行的。

认为这个例子会回答你的问题，但为了方便起见，我将修改一个不同的节点。我对 zipper 功能的了解
lens比较浅。阅读和习惯
lens包与许多其他包相比，但后来它还不错。在这篇文章之前，我没有使用过镜头包中的 zipper 模块或树形模块。
show 的树不太好因此，如果我有时间，我会回来添加一些 pretty-print 输出，否则可能是使用这些示例在 repl 中工作以查看发生了什么的关键。

查看

如果要查看第一个节点的值，根据tree lens package这被称为根，那么您可以:

zipperTree & downward root & view focus

修改

要修改该值并重新创建树(重新压缩树):

zipperTree & downward root & focus .~ 10 & rezip

如果你想向下移动分支，那么你需要使用 downward branches .这是一个修改第一个分支的根并重新压缩树的示例:

zipperTree & downward branches 
           & fromWithin traverse 
           & downward root 
           & focus .~ 5 
           & rezip

在这里，我向下移动到分支列表。然后我使用 fromWithin使用使用 traverse遍历列表，如果这是一个元组，我可以使用 both反而。

保存和重放遍历路径
saveTape和 restoreTape允许您将您的位置保存在 zipper 中，以便以后可以恢复。

保存位置:

tape = zipperTree & downward branches 
                  & fromWithin traverse 
                  & downward root 
                  & saveTape

然后通过树重新创建遍历，我可以:

t <- (restoreTape tape testTree)

然后你可以使用 t 作为新的 zipper 并像往常一样修改它:

t & focus .~ 15 & rezip

磁带会重播您采取的步骤，以便可以在其他树上工作，因此以下内容将与上述磁带一起工作:

testTree2 = Node 1 [ Node 2 [] ]
t2 <- (restoreTape tape testTree2)
t2 & focus .~ 25 & rezip

修改多个位置

如果您想修改多个根，请不要重新拉上 zipper 。下面修改了testTree2的两个根:

zipper testTree2 & downward root 
                 & focus .~ 11 
                 & upward 
                 & downward branches 
                 & fromWithin traverse 
                 & downward root 
                 & focus .~ 111 
                 & rezip