트리에서 노드의 부모 노드에 액세스 할 수있는 트리 구현이 필요합니다. 나는 트리 노드 Tree a이있는 경우DataTree (haskell)에서 노드의 부모 가져 오기
data Tree a = Node {
rootLabel :: a, --^label value
subForest :: Forest a --^zero or more child trees
}
그래서 나는 그것의 레이블과 자식에 액세스 할 수 있습니다 Data.Tree 보면서 나는 트리 정의를 참조하십시오. 하지만 부모 노드에 액세스 할 수도 있습니다. 필요에 따라 다른 구현을 선택해야합니까? 어떤 패키지를 권하고 싶습니까?
이 시도 :
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
이미 이러한 데이터 유형을 제공하는 라이브러리를 알고 있습니까? –
아니요, 저는이 일을하고 싶지 않았습니다. –
코드에서''@ (...)''을 의미합니까? –
Data.Tree 의도적으로 노드는 자신의 부모를 참조 할 필요가 없습니다. 이렇게하면 상위 노드 (또는 다른 분기의 노드)를 변경하면 전체 트리를 다시 만들 필요가 없으며 메모리의 노드를 여러 트리와 공유 할 수 있습니다. 이와 같은 구조의 용어는 "영구적"입니다.
자신의 부모를 알고있는 노드를 구현할 수 있습니다. 결과 구조는 지속되지 않습니다. 명확한 대안은 항상 트리의 루트 노드가 어디에 있는지를 아는 것입니다. 그것은 모든 언어에서 좋은 습관입니다.
Data.Tree이 부모임을 알 수있는 라이브러리는 rosezipper, documentation can be found here입니다.
내가 실수하지 않는다면, 당신이 묻는 것은 기본적으로 LYAH's section on Zippers에 구현되는 것입니다.
나는 그것을 더 잘 설명하려고하지는 않겠지 만, 기본적인 생각은 당신이 나무를 가로 지르는 동안 어떤 나무가 당신에게서 왔는지, 어떤 나뭇 가지를 내려 왔는지 추적하는 것입니다 . 노드의 부모를 데이터 구조에서 직접 추적하지는 않지만 트리를 탐색 할 때 모든 정보를 사용할 수 있습니다.
_Why_ 올라가시겠습니까? 'a'를 수정하려면 [Zippers] (http://www.haskell.org/haskellwiki/Zipper)를 살펴보십시오. 그것은 'Comonad'와 같은 무서운 단어가있는 깊은 토끼 구멍입니다. (Monads IMHO보다 쉽습니다.) – Franky
부모에게 전달하는 함수를 작성해야합니다. 예 :'findPath :: Eq a => a -> Tree a -> [Tree a]'. 전체 트리의 일부를 변경하려면'updateNode :: Eq a => a -> ([Tree a] -> Tree a) -> Tree a -> Tree a'와 같은 함수를 작성하십시오. 그것은 정말로 당신이하려고하는 것에 달려 있습니다. – Vektorweg