Data Structure | Zipper Tree (feat. 함수형 언어)

https://en.wikipedia.org/wiki/Zipper_(data_structure) 

Zipper (data structure) - Wikipedia

 

목표

* Zipper 트리 구조 이해

* 그림 / 코드로 표현

* goLeft, goRight, goUp, goDown 함수 구현

 

---

Zipper란?

순수 함수형 프로그래밍 언어에서 탐색/업데이트에 편리하도록 만든 데이터 구조

 

Zipper 데이터 구조는 

재귀적으로 정의된 데이터 구조에 적용하기 쉽다. 

 

지퍼 트리는 컴퓨터 파일 시스템이랑 비슷하다. 

cd .. > 부모에게 가는 작업

cd subdir > 아래로 가는 작업

즉, 지퍼는 현재 경로에 대한 포인터격이다. 

 

---

http://learnyouahaskell.com/zippers

Zippers - Learn You a Haskell for Great Good!

 

=> 역시 함수형 언어에서 사용되는 자료구조인지, 하스켈 자료가 나온다.

 

 1. 발단

하스켈의 순수성을 이용해서 다른 방식으로 문제를 해결해야 한다. 

참조 투명성이라는 특성 때문에, Haskell과 동일한 것을 나타내는 경우 하나의 값이 다른 것과 일치한다. 

그.래.서. 위치 정보(포인터격)이 필요한 것이다. 

 

지퍼 자료구조에서는 지퍼 트리의 루트에서 변경하려는 요소 까지의 경로를 기억해둔다. 

상위 구조에서 왼쪽 > 오른쪽 > 왼쪽 등등 이렇게 내려갈 것이다. 

 

2. 들어가기

 

기본 트리 데이터 구조

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

 

트리의 예시

freeTree :: Tree Char  
freeTree =   
    Node 'P'  
        (Node 'O'  
            (Node 'L'  
                (Node 'N' Empty Empty)  
                (Node 'T' Empty Empty)  
            )  
            (Node 'Y'  
                (Node 'S' Empty Empty)  
                (Node 'A' Empty Empty)  
            )  
        )  
        (Node 'L'  
            (Node 'W'  
                (Node 'C' Empty Empty)  
                (Node 'R' Empty Empty)  
            )  
            (Node 'A'  
                (Node 'A' Empty Empty)  
                (Node 'C' Empty Empty)  
            )  
        )

 

match a with 와 같은 패턴 매칭 말고, 

더 효율적으로 자료의 값을 업데이트하는 방식이 없을까? 

 

그래서 이 글에서는 Direction이라는 타입을 만들어주었다. 

data direction에는 L, R이 있고, 

type directions에는 루트부터 도착하기까지 거치는 direction을 list 구조로 표현한다. 

 

data Direction = L | R deriving (Show)  
type Directions = [Direction]  
  
changeToP :: Directions-> Tree Char -> Tree Char  
changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r  
changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)  
changeToP [] (Node _ l r) = Node 'P' l r

 

아.. 글이 너무 길다;