트리 순회 혼란?

Question

I가 다음 데이터 유형 (출처 : http://learnyouahaskell.com/zippers) :

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

내가 다음 방향 지침에 따라 노드를 트리를 통과하고 대신 다음과 같은 기능이 있습니다

data Direction = L | R deriving (Show, Eq, Ord) 
type Directions = [Direction] 

changeNode :: Directions -> Tree Char -> Tree Char 
changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r 
changeNode (R : ds) (Node x l r) = Node x l (changeNode ds r) 
changeNode [] (Node _ l r) = Node 'P' r l 

그러나이 I 함수의이 측면을 이해하지 못한다 :

changeNode (L : ds) (Node x l r) = Node x (changeNode ds l) r 

나는 이것이 재귀 (changeNode d s는),하지만 이해가 안 돼 왜 이것은 재귀를 사용하고 있습니다.

누구나 간단한 설명이 있습니까?

Answer 1

이것은 간단한 설명이 아니지만 간단한 예를 시도해 보는 것이 도움이 될 수 있습니다. 연필과 종이 편리와 다음을 읽고 자신을 위해 모든 것을 확인하려고 :

changeNode [L,R] 
    (Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty)) 

를 내가 바로 노드 '에이 이 노드'B '로 좌회전해야 다음 지점과 동의합니다 가정 C '브랜치가 결국'C '를'P '로 대체합니다.

어떻게하면 되나요? 음, 위의 표현식은 changeNode의 첫 번째 패턴과 일치합니다.이 패턴은 유형 선언 직후입니다. 특히, 변수 할당과 일치합니다 : ds = [R], x = 'A', l = 전체 노드 'B'분기, r = 전체 노드 'D'분기. 따라서 일치하는 패턴에 해당하는 오른쪽을 사용하여 다시 쓸 수 있습니다. 패턴의 오른쪽은 다음과 같습니다

Node x (changeNode ds l) r 

과 일치하는 변수를 대체하여 제공합니다

이

Node 'A' (changeNode [R] (Node 'B' Empty (Node 'C' Empty Empty))) 
     (Node 'D' Empty Empty) -- (1) 

지금 무슨 일이 있었 무엇을 볼 수 있습니까? changeNode의 첫 번째 패턴은 방향 목록 ([L, R]에서 [R]로 변경됨)의 첫 번째 문자를 "소비"하고 changeNode 호출을 왼쪽 분기로 푸시 다운합니다.

이제이 재귀 적 changeNode 호출의 값에 집중하십시오. 이번에는 changeNode의 두 번째 패턴 (ds = [], x = 'B', l = Empty 및 r = (Node 'C'Empty Empty))과 일치합니다. 이 패턴의 RHS는 :

는

Node x l (changeNode ds r) 

(해당 subtitutions 포함)로되는 :

Node 'B' Empty (changeNode [] (Node 'C' Empty Empty)) 

및 광고에 다시이 값을 대입 (1), 우리는 얻을 :

Node 'A' (Node 'B' Empty (changeNode [] (Node 'C' Empty Empty))) 
     (Node 'D' Empty Empty) -- (2) 

다시 말하지만이 두 번째 호출이 방향 벡터에서 'R'을 소비하고 노드 'B'의 오른쪽 분기로 changeNode 호출을 밀어 넣은 방법을 참조하십시오. 마지막으로,이 마지막 재귀 changeNode 호출의 값은 무엇입니까?음, L = 빈과 R = 우변 값주고 빈과 세 번째 패턴과 일치 :

Node 'P' Empty Empty 

을 라인에 대체를 (2), 우리가 얻을 :

Node 'A' (Node 'B' Empty (Node 'P' Empty Empty)) (Node 'D' Empty Empty) 

이었다 정확하게 우리는 원했다. 모든 정의는 비 재귀 있었다면 일어 났을 것에

명암이 경우

changeNode' :: Directions -> Tree Char -> Tree Char 
changeNode' (L : ds) (Node x l r) = Node x l r 
changeNode' (R : ds) (Node x l r) = Node x l r 
changeNode' [] (Node _ l r) = Node 'P' r l 

, 우리의 간단한 예는 DS의 =로 다시 [R]를 상기 제 1 패턴과 일치했을 , x = 'A', l = 노드 B의 모든 브랜치, r = 모든 노드의 'D'브랜치, 그러나 라인 (1) 대신에 우리는 비회원의 오른쪽 노드 인 "Node xlr" (1) 대신에 다음을 얻으십시오 :

Node 'A' (Node 'B' Empty (Node 'C' Empty Empty)) (Node 'D' Empty Empty) 

재귀 호출이 없으면 changeNode '가'L '을 소비 한 후 작업이 완료됩니다. 더 이상 처리하지 않고 원래 트리를 반환합니다. 재귀 호출은 방향 벡터가 비어 있고 세 번째 패턴 (실제로 노드를 변경하는 유일한 패턴)이 트리의 올바른 위치에 적용될 때까지 프로세스를 계속 이동하는 데 필요합니다.

위의 예제를 수행 할 때까지 간단한 설명은 changeNode의 처음 두 개 패턴을 ​​사용하여 changeNode 호출을 트리 구조를 통해 changeNode 호출로 이동하는 것입니다. 노드 값을 변경하기 위해 마지막 패턴이 적용되는 최종 대상 노드.