带透镜和拉链的遍历树

Question

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

有人能告诉我如何使用拉链从镜头遍历一棵树吗？特别是,如何编写一个带有根列表并允许我访问子树分支的函数？

假设我有这棵树.如果我的输入是[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中进行实验以了解新代码,因此对于像我这样的人,我创建了一个Haskell学校的帖子/页面,它带有以下示例,但它们是可编辑和可运行的.

认为这个例子会回答你的问题,但为了方便我将修改一个不同的节点.我对镜头拉链功能的了解 相当浅薄.与许多其他包相比,阅读和习惯镜头包中的类型需要更长的时间 ,但之后它也不错.在这篇文章之前,我没有在镜头包装中使用过拉链模块或树模块.

树木不是很好,show所以如果我有时间我会回来并添加一些漂亮的打印输出,否则它可能是使用这些例子在repl中工作的关键,看看发生了什么.

查看

如果我想查看第一个节点的值,根据树镜头包这被称为根,那么你可以:

zipperTree & downward root & view focus

修改

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

zipperTree & downward root & focus .~ 10 & rezip

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

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

在这里,我向下移动到分支列表.然后我使用fromWithinuse use traverse来遍历列表,如果这是一个我可以使用的元组both.

保存和重放遍历路径

saveTape并restoreTape允许您将您的位置保存在拉链中,以便后者可以恢复.

保存职位:

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

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

t <- (restoreTape tape testTree)

然后你可以使用t作为新拉链并正常修改它:

t & focus .~ 15 & rezip

磁带重放您采取的步骤,因此可以在其他树上工作,因此以下将适用于上面定义的磁带:

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

修改多个位置

如果你想修改多个根,只需重新拉紧拉链即可.以下修改了testTree2的两个根:

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