题 带透镜和拉链的遍历树


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

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

假设我有这棵树。如果我的意见是 [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)?


15
2018-03-19 00:15


起源




答案:


编辑:我通常在ghci中试验以理解新代码,所以对于像我这样的人我创建了一个 哈斯克尔学院的帖子/页面 它带有以下示例,但它们是可编辑和可运行的。


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

树木不太好用 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

在这里,我向下移动到分支列表。然后我用 fromWithin 使用 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

16
2018-03-19 01:01



谢谢你。但是,它并没有完全解决我的作业(只是开玩笑)。我不是要修改特定节点。相反,我希望遍历整个树,并记录到满足某些条件的某个节点的路径。在“修改”示例中,您知道路径是 zipperTree & within (root.traverse.branches) >>= saveTape。我想知道如何在不知道它的情况下(通过遍历它)获得路径。 - Kai
具有更多细节的具体示例将是有用的。使用上面的原语和递归,可以访问树中的每个节点,查看每个值并对其应用测试。测试成功后,您只需返回磁带或将其保存在状态或编写器monad中,如果这对您的应用程序更好。 - Davorak
这非常有帮助!如何在我自己的树类型上使用Data.Tree.Lens?具体来说,如果它是二叉树而不是玫瑰树呢? - nont
@nont root和branches只是为玫瑰树定义的镜头。所以我会用 makeLenses一个TH助手,为我的自定义数据结构生产镜头,不管是树还是其他。然后用 downward, focus, upward, fromWithin,和 rezip 像平常一样。 - Davorak


根据我的经验,你通常不想要一个 拉链。在这种情况下,您可以定义一个 穿越 这将允许您在给定根节点路径的情况下访问子林。

-- Make things a little easier to read
leaf :: a -> Tree a
leaf = return

testForest :: Forest Int
testForest = [ Node 1 [ Node 2 [ Node 4 [ leaf 6, leaf 8]
                               , Node 5 [ leaf 7, leaf 9]]
                      , Node 3 [ leaf 10, leaf 11]]]

-- | Handy version of foldr with arguments flipped
foldEndo :: (a -> b -> b) -> [a] -> b -> b
foldEndo f xs z = foldr f z xs

-- | Traverse the subforests under a given path specified by the values of
-- the parent nodes.
path :: Eq a => [a] -> Traversal' (Forest a) (Forest a)
path = foldEndo $ \k ->     -- for each key in the list
       traverse               -- traverse each tree in the forest
     . filtered (hasRoot k)   -- traverse a tree when the root matches
     . branches               -- traverse the subforest of the tree

  where
  hasRoot :: Eq a => a -> Tree a -> Bool
  hasRoot k t = k == view root t

-- | Helper function for looking at 'Forest's.
look :: Show a => Forest a -> IO ()
look = putStr . drawForest . (fmap . fmap) show

-- Just show 'path' in action

demo1 = look $ testForest & path [1,3] .~ []
demo2 = look $ testForest & path [1,3] . traverse . root *~ 2
demo3 = look $ testForest ^. path [1,3]
demo4 = [] == testForest ^. path [9,3]
demo5 = traverseOf_ (path [1,3]) print testForest

4
2018-05-09 22:58