обходное дерево с объективом и молниями

Question

Я изучаю пакет объектива. Должен сказать, что это довольно сложная задача.

Может ли кто-нибудь показать мне, как пройти дерево с молнией от объектива? В частности, как я могу написать функцию, которая принимает список корней и позволяет мне получить доступ к ветвям поддерева?

Предположим, у меня есть это дерево. Если мой вход [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)?

Answer 1

Редактировать: Я обычно экспериментирую в ghci, чтобы понять новый код, поэтому для таких, как я, я создал School of Haskell post/page, который поставляется с приведенными ниже примерами, но они доступны для редактирования и запуска.

---

Подумайте, эти примеры ответят на ваши вопросы, но для целесообразности я собираюсь изменить другой узел. Мои знания о функциях застежки-молнии в lens довольно мелкие. Потребуется немного больше времени, чтобы читать и привыкать к типам в пакете lens по сравнению со многими другими пакетами, но потом это неплохо. Перед этим сообщением я не использовал модуль молнии или модуль дерева в пакете объектива.

Деревья не очень хорошо сочетаются с show, поэтому, если у меня есть время, я вернусь и добавлю довольно красивую печать, иначе это, вероятно, ключ к работе в реплике с этими примерами, чтобы увидеть, что происходит.

Просмотр

Если я хочу, чтобы просмотреть значение первого узла, в соответствии с tree lens package этом упоминается как корень, то вы можете:

zipperTree & downward root & view focus 

Изменение

Для изменить это значение и воссоздать дерево (rezip the tree):

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 & focus .~ 15 & rezip 

Лента повторяет шаги, которые вы предприняли, поэтому может работать на других деревьях, поэтому последующие будут работать с t он лента, как определено выше:

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 

Answer 2

В моем опыте, как правило, не хотят иметь Zipper. В этом случае вы можете определить Traversal, который позволит вам получить доступ к подпоследовательности с учетом пути корневых узлов.

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