在Haskell中使用镜头遍历和添加元素到Data.Tree

-2

我开始使用镜头，直到现在我一直无法在我正在编写的代码库的具体部分中使用它们。我的目标是通过在现有的节点中添加新节点来更新玫瑰树结构，例如Data.Tree中的玫瑰树结构。要做到这一点我认为这将是有意义的标识具有唯一ID的每个节点，因此它看起来就像是：在Haskell中使用镜头遍历和添加元素到Data.Tree

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 :)’

谢谢！

来源

2017-04-02 Jesuspc

稍作澄清：是“path”的'originalTree'部分的根？ – duplode

在我的伪实现过程中，我没有将它包含在路径中，但它在那里有意义。我会说是的。 – Jesuspc

“逆变”用于获取，您想设置，并且您从不使用'cmap'。从traversalPath中删除'Contravariant'约束。 – Gurkenglas

这不是特别优雅，但应该做的伎俩：

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 = []}]}

请注意，我们正在处理遍历，而不是与镜头 - 有没有G保证或期望路径的目标存在或者是独特的。

这里是一个更具风格的变体，没有head和使用alaf来处理Endo包装。

addToTree :: Eq a => NonEmpty a -> Tree a -> Tree a -> Tree a 
addToTree (desiredRoot :| path) newNode [email protected](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

来源

2017-04-02 21:10:15 duplode

在Haskell中使用镜头遍历和添加元素到Data.Tree

回答

相关问题