Drzewo przejścia z soczewkami i zamkami

Question

Uczę się pakietu Lens. Muszę powiedzieć, że to dość trudne zadanie.

Czy ktoś może mi pokazać, jak przejść drzewo z zamkiem błyskawicznym z obiektywu? W szczególności, w jaki sposób mogę napisać funkcję, która pobiera listę korzeni i pozwala mi uzyskać dostęp do gałęzi pod-drzewa?

Załóżmy, że mam to drzewo. Jeśli moje wejście jest [1, 3] funkcja powinna pozwolić mi dostęp węzeł 10 i 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 

Ponadto, jak dokładnie używać saveTape i restoreTape zapisać ścieżkę przejścia (do StateT lub IORef)?

Answer 1

edytuj: Zazwyczaj eksperymentuję z ghci, aby zrozumieć nowy kod, więc dla takich jak ja stworzyłem School of Haskell post/page, który pochodzi z poniższych przykładów, ale są one edytowalne i można je uruchomić.

---

Pomyśl o tym, że te przykłady odpowiedzą na twoje pytania, ale z powodów praktycznych zamierzam zmodyfikować inny węzeł. Moja znajomość funkcji zamka błyskawicznego w lens jest raczej płytka. Trochę dłużej trwa czytanie i przyzwyczajenie się do typów w pakiecie lens w porównaniu do wielu innych pakietów, ale potem nie jest źle. Przed tym postem nie użyłem modułu zamka błyskawicznego ani modułu drzewa w pakiecie soczewek.

Drzewa nie są całkiem niezłe z show, więc jeśli będę mieć czas, powrócę i dodaję całkiem niezłe wydruki, w przeciwnym razie prawdopodobnie kluczem będzie praca w repl z tymi przykładami, aby zobaczyć, co się dzieje.

Przedstawiamy

Jeśli chcę zobaczyć wartość pierwszego węzła, w zależności od tego tree lens package jest określany jako root, następnie możesz:

zipperTree & downward root & view focus 

Modyfikowanie

Aby zmodyfikuj tę wartość i odtwórz drzewo (rezip the tree):

zipperTree & downward root & focus .~ 10 & rezip 

Jeśli chcesz przesunąć gałęzie, musisz użyć downward branches. Oto przykład, który modyfikuje katalog główny pierwszej gałęzi i rezipx drzewa:

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

Tutaj przechodzę w dół do listy oddziałów. Następnie używam fromWithin użyć użyć traverse do przechodzenia przez listę, jeśli to była krotka, mógłbym zamiast tego użyć both.

zapisywanie i odtwarzanie ścieżek traversal

saveTape i restoreTape pozwolić, aby zapisać pozycję na zamek błyskawiczny, dzięki czemu może on zostać przywrócony ostatni.

Zapisz stanowisko:

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

Następnie odtworzyć przechodzenie przez drzewa mogę:

t <- (restoreTape tape testTree) 

Następnie można użyć t jako nowy zamek błyskawiczny i zmodyfikować go jako normalny:

t & focus .~ 15 & rezip 

Taśma odtwarza kroki, które wykonałeś, dzięki czemu może pracować na innych drzewach, więc obserwacja zadziała z on tape jak zdefiniowano powyżej:

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

Modyfikacja wielu lokalizacjach

Jeśli chcesz zmodyfikować wiele korzenie po prostu trzymać się na reziping zamek. Poniższa modyfikuje dwa korzenie testTree2:

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

Answer 2

Z mojego doświadczenia wynika, zazwyczaj nie chcą Zipper. W tym przypadku możesz zdefiniować Traversal, która pozwoli ci uzyskać dostęp do subdomenów podanych ścieżce węzłów głównych.

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