17

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

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

假设我有这棵树。如果我的输入是[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）？

4

2 回答 2

17

edit: I normally experiment in ghci to understand new code so for those like myself I have created a School of Haskell post/page which comes with the below examples but they are editable and runnable.

Think this examples will answer your questions but for expediency I am going to modify a different node. My knowledge of the zipper functions in the lens is rather shallow. It takes a little longer to read and get used to the types in the lens package compared to many other packages, but afterwards it is not bad. I had not used the zipper module or the tree module in the lens package before this post.

The trees do not pretty pretty well with show so if I have time I will come back and add some pretty printed out put otherwise it is probably key to work in the repl with these examples to see what is happening.

Viewing

If I want to view the value of the first node, according to the tree lens package this is referred to as the root, then you can:

zipperTree & downward root & view focus

Modifying

To modify that value and recreate the tree(rezip the tree):

zipperTree & downward root & focus .~ 10 & rezip

If you wanted to move down the branches then you need to use downward branches. Here is an example that modifies the root of the first branch and rezipx the tree:

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

Here I move downward to the list of branchs. I then use fromWithin use use traverse to traverse the list, if this was a tuple I could use both instead.

Saving and replaying traversal paths

saveTape and restoreTape allow for you to save your position in the zipper so that it can be restored latter.

Save a position:

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

Then to recreate the traversal through the tree I can:

t <- (restoreTape tape testTree)

Then you can use t as the new zipper and modify it as normal:

t & focus .~ 15 & rezip

The tape replays the steps that you took so can work on other trees so the follow would work with the tape as defined above:

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

Modifying Multiple locations

If you want to modify multiple roots just hold off on reziping the zipper. The following modifies the two roots of testTree2:

zipper testTree2 & downward root 
                 & focus .~ 11 
                 & upward 
                 & downward branches 
                 & fromWithin traverse 
                 & downward root 
                 & focus .~ 111 
                 & rezip
于 2013-03-19T01:01:08.790 回答
4

根据我的经验，您通常不需要Zipper。在这种情况下，您可以定义一个遍历，它允许您访问给定根节点路径的子林。

-- 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
于 2013-05-09T22:58:41.963 回答