在Data.Tree（haskell）中獲取節點的父節點

我需要一個樹實現，我可以訪問樹中任何節點的父節點。看着Data.Tree我看樹的定義：在Data.Tree（haskell）中獲取節點的父節點

data Tree a = Node { 
    rootLabel :: a,   --^label value 
    subForest :: Forest a --^zero or more child trees 
}

所以，如果我有一個樹節點Tree a我可以訪問它的標籤和它的孩子。但是也可以訪問其父節點？必須爲我的需求選擇不同的實施方案嗎？你會推薦哪個軟件包？

來源

2014-03-28 Stephan Kulla

_你爲什麼要去？如果你想修改一些''''，看看[拉鍊]（http://www.haskell.org/haskellwiki/Zipper）。這是一個深深的兔子洞，像「Comonad」這樣可怕的詞。（這比Monads恕我直言。）更容易 – Franky

你應該寫一個函數來交付你的父母。例如：'findPath :: Eq a => a - > Tree a - > [Tree a]'。如果你想改變完整樹的部分，寫一個類似於'updateNode :: Eq a => a - >（[Tree a] - > Tree a） - > Tree a - > Tree a'的函數。這真的取決於你想做什麼。 – Vektorweg

試試這個：

data Tree a = Leaf | Node a (Tree a) (Tree a) (Tree a) deriving (Eq, Show)

您可以將父樹保存到第三（或任何其他）樹。例子：

singleton::(Ord a)=>a->Tree a 
singleton x = Node x Leaf Leaf Leaf 
insert::(Ord a)=>a->Tree a->Tree a 
insert x Leaf = singleton x 
insert x [email protected](Node a l r p) = insertIt x t p 
where insertIt x Leaf (Node a l r p) = Node x Leaf Leaf (Node a Leaf Leaf Leaf)--1* 
     insertIt x [email protected](Node a l r p) parent 
     | x == a = t 
     | x < a = Node a (insertIt x l t) r p 
     | x > a = Node a l (insertIt x l t) p

1此行*您可以保存整個父：

where insertIt x Leaf parent = Node x Leaf Leaf parent

來源

2014-03-28 19:21:15

你知道一個圖書館已經提供這樣的數據類型嗎？ –

不，我從來不想這樣做。 –

你的代碼中的「t @（...）」是什麼意思？ –

Data.Tree故意沒有節點引用自己的父母。這樣，對父節點（或其他分支中的節點）的更改不需要重新創建整個樹，並且內存中的節點可以與多個樹共享。像這樣的結構的術語是「持久的」。

你可以實現一個知道它自己父節點的節點;由此產生的結構將不會持久。明確的選擇是始終知道樹的根節點在哪裏;這是任何語言的良好習慣。

一個庫允許Data.Tree知道它的父母是rosezipper，documentation can be found here。

來源

2014-03-28 19:35:40 WolfeFan

如果我沒有弄錯，你要求的基本上是在LYAH's section on Zippers中實現的。

我不會試圖比Miran更好地解釋它，但基本的想法是跟蹤你來自哪棵樹，以及你在向下移動哪一個分支，而在遍歷樹時。您不直接在數據結構中跟蹤節點的父節點，但所有信息在遍歷樹時都可用。

來源

2014-03-28 20:10:40

在Data.Tree（haskell）中獲取節點的父節點

回答

相關問題