I'm learning the Lens package. I must say it's a rather challenging task.

Can someone show me how to traverse a Tree with Zipper from Lens? In particular, how can I write a function that takes a list of roots and allows me to access the branches of the sub-tree?

Suppose I have this tree. If my input is [1, 3] , the function should allow me access node 10 and 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

In addition, how exactly do I use saveTape and restoreTape to save the traversal path (to a StateT or IORef)?

---

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

---

In my experience, you typically don't want a Zipper . In this case you can define a Traversal which will allows you to access subforests given a path of root nodes.

-- 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

链接地址: http://www.djcxy.com/p/58760.html

上一篇: 分离模型和GUI IO（Wx）的状态：堆栈还是FRP？

下一篇: 透镜和拉链的遍历树