cây ngang với Ống kính và Dây khóa kéo

Question

Tôi đang tìm hiểu gói Ống kính. Tôi phải nói đó là một nhiệm vụ khá khó khăn.

Ai đó có thể chỉ cho tôi cách di chuyển cây bằng dây kéo từ ống kính không? Đặc biệt, làm thế nào tôi có thể viết một hàm lấy danh sách các gốc và cho phép tôi truy cập vào các nhánh của cây con?

Giả sử tôi có cây này. Nếu đầu vào của tôi là [1, 3], chức năng nên cho phép tôi nút truy cập 10 và 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 

Bên cạnh đó, làm thế nào chính xác để tôi sử dụng saveTape và restoreTape để lưu các con đường traversal (một StateT hoặc IORef)?

Answer 1

chỉnh sửa: Tôi thường thử nghiệm trong ghci để hiểu mã mới để những người như tôi đã tạo một School of Haskell post/page đi kèm với các ví dụ bên dưới nhưng chúng có thể chỉnh sửa và chạy được.

---

Hãy suy nghĩ ví dụ này sẽ trả lời câu hỏi của bạn nhưng để thực hiện, tôi sẽ sửa đổi một nút khác. Kiến thức của tôi về các chức năng của dây kéo trong số lens khá nông. Phải mất nhiều thời gian hơn để đọc và làm quen với các loại trong gói lens so với nhiều gói khác, nhưng sau đó nó không phải là xấu. Tôi đã không sử dụng mô-đun dây kéo hoặc mô-đun cây trong gói thấu kính trước bài đăng này.

Cây không đẹp lắm với show vì vậy nếu tôi có thời gian, tôi sẽ quay lại và thêm một số chữ được in ra nếu không, đó có thể là chìa khóa để làm việc trong repl với các ví dụ này để xem điều gì đang xảy ra.

Xem

Nếu tôi muốn xem giá trị của nút đầu tiên, theo tree lens package này được gọi là gốc rễ, sau đó bạn có thể:

zipperTree & downward root & view focus 

Sửa đổi

Để sửa đổi giá trị đó và tạo lại cây (giải nén cây):

zipperTree & downward root & focus .~ 10 & rezip 

Nếu bạn muốn di chuyển xuống các nhánh thì bạn cần sử dụng downward branches. Dưới đây là ví dụ sửa đổi gốc của nhánh đầu tiên và giải nén cây:

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

Ở đây tôi chuyển xuống danh sách chi nhánh. Sau đó tôi sử dụng fromWithin sử dụng sử dụng traverse để duyệt qua danh sách, nếu đây là một bộ tôi có thể sử dụng both thay thế.

tiết kiệm và phát lại traversal đường

saveTape và restoreTape cho phép bạn lưu vị trí của bạn trong dây kéo để nó có thể được phục hồi sau.

Lưu vị trí:

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

Sau đó, để tái tạo traversal qua cây Tôi có thể:

t <- (restoreTape tape testTree) 

Sau đó, bạn có thể sử dụng t là dây kéo mới và sửa đổi nó như bình thường:

t & focus .~ 15 & rezip 

Băng phát lại các bước mà bạn đã thực hiện để có thể làm việc trên các cây khác để theo dõi sẽ hoạt động với t ông băng như đã định nghĩa ở trên:

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

Sửa đổi Nhiều địa điểm

Nếu bạn muốn thay đổi nhiều rễ chỉ cần giữ tắt trên reziping dây kéo. Sau đây sẽ thay đổi hai gốc rễ của testTree2:

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

Answer 2

Theo kinh nghiệm của tôi, bạn thường không muốn có một Zipper. Trong trường hợp này, bạn có thể xác định Traversal cho phép bạn truy cập các tiểu khu được cung cấp đường dẫn của nút gốc.

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