Haskellでレンズを使用してData.Treeに移動して要素を追加する

Question

レンズを使用し始めていますが、今まで私が書いているコードベースの具体的な部分では使用できませんでした。私の目的は、既存のものの1つの中に新しいノードを追加することによって、Data.Treeにあるようなバラのツリー構造を更新することです。それはそのようになりますので、そうするために、私は、それが一意のIDと各ノードを識別するために理にかなっていることを考えた：

type MyTree = Tree Id 
type Path = [Id] 

addToTree :: MyTree -> MyTree -> Path -> MyTree 
addToTree originalTree newNode path = undefined 

機能addToTreeは、IDのパスに従うことによってoriginalTreeを横断し、追加する必要がありますそのレベルのnewNodeが更新されたツリー全体を返します。私はそれをゲッターにするのに問題はなかったが、私は手術で適切なレンズを見つけることができない。私が今まで持っているものだ

：

import   Control.Lens 
import   Data.Tree 
import   Data.Tree.Lens 

addToTree :: MyTree -> Path -> MyTree -> MyTree 
addToTree tree path branch = tree & (traversalPath path) . branches %~ (branch:) 

traversalPath :: (Foldable t, Applicative f, Contravariant f) => t Id -> (MyTree -> f MyTree) -> MyTree -> f MyTree 
traversalPath = foldl (\acc id-> acc . childTraversal id) id 

childTraversal :: (Indexable Int p, Applicative f) => Id -> p MyTree (f MyTree) -> MyTree -> f MyTree 
childTraversal id = branches . traversed . withId id 

withId :: (Choice p, Applicative f) => Id -> Optic' p f MyTree MyTree 
withId id = filtered (\x -> rootLabel x == id) 

しかし、それはとコンパイルに失敗します。

• No instance for (Contravariant Identity) 
    arising from a use of ‘traversalPath’ 
• In the first argument of ‘(.)’, namely ‘(traversalPath path)’ 
    In the first argument of ‘(%~)’, namely 
    ‘(traversalPath path) . branches’ 
    In the second argument of ‘(&)’, namely 
    ‘(traversalPath path) . branches %~ (branch :)’ 

ありがとう！

Answer 1

これは、特別にエレガントではありませんが、トリックを行う必要があります。

import Control.Lens 
import Data.Monoid (Endo(..)) -- A tidier idiom for 'foldr (.) id'. 
import Data.List.NonEmpty (NonEmpty(..)) -- You don't want an empty path. 
import qualified Data.List.NonEmpty as N 
import Data.Tree 
import Data.Tree.Lens -- That's where I got 'branches' from. 

addToTree :: Eq a => NonEmpty a -> Tree a -> Tree a -> Tree a 
addToTree path newNode oldTree = head $ over pathForests (newNode :) [oldTree] 
    where 
    pathForests = appEndo $ foldMap (Endo . goDown) path 
    goDown x = traverse . filtered ((x ==) . rootLabel) . branches 

（具体的には、私は決しても、それはおそらく失敗することはできませんここで、このようなケースでは、headを使用してなどをお気軽にお気に入りの婉曲でそれを置き換えるために）

デモ：。

GHCi> addToTree (1 :| []) (Node 2 []) (Node 1 []) 
Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = []}]} 
GHCi> addToTree (4 :| []) (Node 2 []) (Node 1 []) 
Node {rootLabel = 1, subForest = []} 
GHCi> addToTree (1 :| [5]) (Node 2 []) (Node 1 [Node 5 [], Node 6 []]) 
Node {rootLabel = 1, subForest = [Node {rootLabel = 5, subForest = [Node {rootLabel = 2, subForest = []}]},Node {rootLabel = 6, subForest = []}]} 
GHCi> addToTree (1 :| [7]) (Node 2 []) (Node 1 [Node 5 [], Node 6 []]) 
Node {rootLabel = 1, subForest = [Node {rootLabel = 5, subForest = []},Node {rootLabel = 6, subForest = []}]} 
GHCi> addToTree (1 :| [5,3]) (Node 2 []) (Node 1 [Node 5 [], Node 6 []]) 
Node {rootLabel = 1, subForest = [Node {rootLabel = 5, subForest = []},Node {rootLabel = 6, subForest = []}]} 

は、我々は、レンズとトラバーサルを扱う、とされていないことに注意してください - 何グラムはありませんパスのターゲットが存在するか、またはユニークであることを保証します。

headを使用せずにを使用して、Endoのラッピングを処理する、より定式化された変形です。

addToTree :: Eq a => NonEmpty a -> Tree a -> Tree a -> Tree a 
addToTree (desiredRoot :| path) newNode oldTree@(Node x ts) 
    | x == desiredRoot = Node x (over pathForests (newNode :) ts) 
    | otherwise = oldTree 
    where 
    pathForests = alaf Endo foldMap goDown path 
    goDown x = traverse . filtered ((x ==) . rootLabel) . branches