Traversal Baum mit Objektiv und Reißverschlüsse

Question

Ich lerne das Lens-Paket. Ich muss sagen, es ist eine ziemlich herausfordernde Aufgabe.

Kann mir jemand zeigen, wie man einen Baum mit Zipper von Lens überquert? Insbesondere, wie kann ich eine Funktion schreiben, die eine Liste von Wurzeln nimmt und mir erlaubt, auf die Zweige des Unterbaums zuzugreifen?

Angenommen, ich habe diesen Baum. Wenn mein Eingang [1, 3] ist, sollte die Funktion erlauben Sie mir, Zugangsknoten 10 und 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 

Darüber hinaus, wie genau verwende ich saveTape und restoreTape den Durchlaufweg zu speichern (zu einem StateT oder IOREF)?

Answer 1

edit: Ich experimentiere normalerweise in ghci, um neuen Code zu verstehen, also für diejenigen wie mich Ich habe eine School of Haskell post/page erstellt, die mit den folgenden Beispielen kommt, aber sie sind editierbar und ausführbar.

Denken Sie, dass diese Beispiele Ihre Fragen beantworten werden, aber aus Zweckmäßigkeit werde ich einen anderen Knoten ändern. Mein Wissen über die Reißverschlussfunktionen in der lens ist eher flach. Es dauert etwas länger zu lesen und sich an die Typen im lens Paket im Vergleich zu vielen anderen Paketen zu gewöhnen, aber danach ist es nicht schlecht. Ich hatte das Reißverschlussmodul oder das Baummodul im Objektivpaket vor diesem Post nicht benutzt.

Die Bäume sind nicht ziemlich gut mit show Also wenn ich Zeit habe, werde ich zurückkommen und fügen Sie einige schön ausgedruckt setzen, sonst ist es wahrscheinlich der Schlüssel zu arbeiten in der Repl mit diesen Beispielen zu sehen, was passiert.

Anzeigen

Wenn ich den Wert des ersten Knotens anzeigen möchten, nach dem tree lens package dieser wird als Wurzel bezeichnet, dann können Sie:

zipperTree & downward root & view focus 

Ändern

zu diesen Wert ändern und den Baum neu (rezip den Baum):

zipperTree & downward root & focus .~ 10 & rezip 

Wenn Sie die Zweige nach unten verschieben möchten, müssen Sie downward branches verwenden. Hier ist ein Beispiel, das die Wurzel des ersten Zweiges modifiziert und rezipx den Baum:

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

hier I nach unten in der Liste des branchs bewegen. Ich benutze dann fromWithin verwenden Sie traverse, um die Liste zu durchlaufen, wenn dies ein Tupel war, könnte ich stattdessen both verwenden.

Speichern und Abspielen Traversal Pfade

saveTape und restoreTape erlauben Sie Ihre Position in der Reißverschluss zu speichern, so dass es letztere wieder hergestellt werden kann.

Speichern einer Position:

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

dann die Traversal durch den Baum neu erstellen Ich kann:

t <- (restoreTape tape testTree) 

Dann können Sie t als neuer Reißverschluss verwenden und es als normal ändern:

t & focus .~ 15 & rezip 

Das Band wiederholt die Schritte, die Sie genommen haben, also kann auf anderen Bäumen arbeiten, also würde das Folgen mit t arbeiten er Band, wie oben definiert:

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

Ändern Mehrere Standorte

Wenn Sie mehrere Wurzeln halten Sie einfach auf reziping den Reißverschluss ändern möchten. Die folgende modifiziert die beiden Wurzeln der testTree2:

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

Answer 2

In meiner Erfahrung, Sie in der Regel wollen keine Zipper. In diesem Fall können Sie einen Traversal definieren, mit dem Sie auf die Unterforstgebiete zugreifen können, die einen Pfad von Wurzelknoten haben.

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