レンズとジッパー付きトラバーサルツリー

Question

私はレンズパッケージを学んでいます。私はそれがむしろ挑戦的な仕事だと言わなければならない。

レンズからZipperを使ってツリーをトラバースする方法を教えてもらえますか？特に、ルーツのリストを取得し、サブツリーのブランチにアクセスするための関数を書くにはどうすればよいですか？

このツリーがあるとします。私の入力が[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 

を許可する必要があり、正確にどのように私は（StateTまたはIORefに）トラバーサルパスを保存するためにsaveTapeとrestoreTapeを使うのですか？

Answer 1

編集：私は通常、新しいコードを理解するためにghciで実験していますので、自分自身のように、私はSchool of Haskell post/pageを作成しましたが、これは編集可能で実行可能です。

---

この例はあなたの質問に答えますが、便宜のために別のノードを変更するつもりです。 のファスナー機能に関する私の知識はかなり浅いです。 パッケージのタイプを他の多くのパッケージに比べて読み込みに時間がかかりますが、その後はそれほど悪くありません。私は、このポストの前にレンズパッケージにジッパーモジュールまたはツリーモジュールを使用していなかった。

ツリーはかなりshowでかなりうまくいきません。時間があれば、私は戻っていくつかかなりのプリントアウトを追加します。それ以外の場合は、これらの例でreplで動作していることを確認する鍵です。

への変更

zipperTree & downward root & view focus 

を：それからすることができます、私は最初のノードの値を表示したい場合は、tree lens packageによると、これはルートと呼ばれている

を表示

その値を変更してツリーを再作成します（ツリーを再圧縮します）。

zipperTree & downward root & focus .~ 10 & rezip 

支店を降りたい場合は、downward branchesを使用する必要があります。最初のブランチのルートを変更し、ツリーをrezipxする例を次に示します。

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

ここで私はブランチのリストに移動します。私はfromWithinを使用してください。traverseを使用してリストを走査してください。これがタプルの場合は、代わりにbothを使用できます。

の保存と再生トラバーサルパス

saveTapeとrestoreTape、それは後者復元することができるように、ジッパーで自分の位置を保存することを可能とします。

保存位置：次に、あなたが新しいジッパーとしてトンを使用し、通常のように変更することができます

t <- (restoreTape tape testTree) 

：

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

その後、私ができるツリーをトラバースを再現する

t & focus .~ 15 & rezip 

テープは、他のツリーでも動作できるように、手順を再生します。あなただけのジッパーをrezipingに延期複数のルートを変更したい場合は、複数の場所に

を変更

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

：上記で定義された彼は、テープ。以下はtestTree2の2つの根を変更します。私の経験で

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

Answer 2

を、あなたは通常、ジッパーを望んでいません。この場合、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