我正在學習鏡頭包。我必須說這是一項頗具挑戰性的任務。鏡頭和拉鍊的遍歷樹

有人可以告訴我如何從鏡頭穿過拉鍊樹嗎？特別是，我該如何編寫一個函數，該函數需要一個根的列表並允許我訪問子樹的分支？

假設我有這棵樹。如果我的輸入爲[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）？

來源

2013-03-19 Kai

編輯：我通常在ghci中試驗以瞭解新代碼，因此對於像我這樣的人，我創建了一個School of Haskell post/page，它附帶下面的示例，但它們是可編輯和可運行的。

認爲這個例子將回答你的問題，但爲了方便，我將修改一個不同的節點。我對 lens中拉鍊功能的瞭解很淺。與許多其他軟件包相比，讀取和習慣 lens軟件包中的類型需要更長的時間，但之後並不差。在本文之前，我沒有使用鏡頭包裝中的拉鍊模塊或樹形模塊。

這棵樹跟show不太相符，所以如果我有時間的話我會回來添加一些漂亮的打印輸出，否則它可能是使用這些例子來查看發生了什麼的關鍵。

查看

如果我想查看第一個節點的值，根據tree lens package此被稱爲根，則可以：

zipperTree & downward root & view focus

修改

要修改該值並重新創建樹（重新壓縮樹）：

zipperTree & downward root & focus .~ 10 & rezip

如果您想要移動分支，那麼您需要使用downward branches。這裏是一個例子，修改第一個分支的根目錄和rezipx樹：

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

這裏我向下移動到分支列表。然後我使用fromWithin使用用途traverse遍歷列表，如果這是一個元組，我可以使用both來代替。

保存和回放遍歷路徑

saveTape和restoreTape允許你保存在你的拉鍊位置，以便可以將其還原後者。

保存的位置：

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

然後重新通過樹，我可以遍歷：

t <- (restoreTape tape testTree)

然後你可以使用T作爲新的拉鍊，並修改它爲正常：

t & focus .~ 15 & rezip

錄像帶重放，你花了這麼可以在其他樹木工作，以便後續將與科技工作的步驟他帶如上定義：

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

修改多個位置

如果要修改多根只是暫緩reziping拉鍊。以下修改testTree2的兩個根：

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

來源

2013-03-19 01:01:08 Davorak

感謝。但是，它並沒有完全解決我的作業（只是在開玩笑）。我不想修改特定的節點。相反，我希望遍歷整個樹，並記錄滿足某些條件的某個節點的路徑。在你的「修改」例子中，你知道路徑是'zipperTree＆within（root.traverse.branches）>> = saveTape'。我想知道如何在事先不知道它的情況下（通過遍歷它）來獲得路徑。 – Kai 2013-03-19 02:42:50

具體更多細節的例子會對你有所幫助。通過上面的原語和遞歸，可以訪問樹中的每個節點，查看每個值並對其應用測試。測試成功後，您只需返回磁帶或將其保存在狀態或寫入器monad中，如果這對您的應用程序更好。 – Davorak 2013-03-19 03:47:14

這非常有幫助！我如何在自己的樹類型上使用Data.Tree.Lens？具體來說，如果它是一棵二叉樹而不是玫瑰樹呢？ – nont 2013-10-20 16:48:39

以我的經驗，你通常不希望拉鍊。在這種情況下，你可以定義一個遍歷這將允許你訪問給定一個根節點路徑的子森林。

-- 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-09 22:58:41 glguy

鏡頭和拉鍊的遍歷樹

回答

查看

修改

保存和回放遍歷路徑

修改多個位置

相關問題