17

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

Nikita Volkov
  • 42,792
  • 11
  • 94
  • 169
Kai
  • 263
  • 1
  • 6

2 Answers2

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
Davorak
  • 7,362
  • 1
  • 38
  • 48
  • Thanks for this. However, it doesn't quite address my homework (just kidding). I'm not trying to modify a particular node. Instead, I wish to traverse the whole tree, and record the path to a certain node that satisfies some condition. In your "modifying" example, you know the path is `zipperTree & within (root.traverse.branches) >>= saveTape`. I was wondering how I can get the path without knowing it before hand (by traversing it). – Kai Mar 19 '13 at 02:42
  • A concrete example with more details would be helpful then. With the primitives above and recursion it is possible to visit every node in the tree,look at each value and apply a test to it. After the test succeeds you would just return the tape or save it in a state or writer monad if that is better for your application. – Davorak Mar 19 '13 at 03:47
  • This is very helpful! How do I use Data.Tree.Lens on my own tree types? Specifically, what if its a binary tree instead of a rose tree? – nont Oct 20 '13 at 16:48
  • @nont root and branches are just lenses defined for the rose tree. So I would use the `makeLenses`, a TH helper, to produces lenses for my custom data structure weather a tree or otherwise. Then use `downward`, `focus`, `upward`, `fromWithin`, and `rezip` as normal. – Davorak Oct 21 '13 at 01:11
4

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
glguy
  • 1,090
  • 7
  • 8