이 글은 책 Learn You a Haskell for Great Good!에서 섹션 Zippers를 읽고 정리한 것이다.
지퍼
하스켈의 순수함이 좋긴 한데 어떨 때는 이 순수함 때문에 문제를 해결할 때 명령형 언어에서 쓰던 방식과는 다르게 접근해야 한다. 참조 투명성(referential transparency) 때문에 값을 바꾸는 게 힘들어서 그렇다.
예를 들어 5로 가득한 나무가 있는데 이 중 하나를 6으로 바꾸고 싶을 때 우리가 바꾸고 싶은 5가 어떤 것인지 알 수 있는 방법이 있어야 한다. 명령형 언어에서는 그 5가 저장된 메모리 주소가 어디인지 확인하고 그냥 값을 바꾸면 된다. 그런데 하스켈에서는 메모리 주소로 값을 구분하는 건 힘들다. 하스켈에서 나무를 바꾼다는 건 나무 하나를 입력으로 받아서 원래 나무랑 비슷하지만 일부만 조금 다른 새 나무를 리턴하는 것이다.
한 가지 방법은 나무 뿌리(root)에서 출발해서 바꾸고 싶은 원소가 있는 곳까지 가는 길을 기억하는 것이다.
왼쪽으로 가, 그 다음엔 오른쪽, 그리고 다시 왼쪽, 자 이제 거기 있는 값을 바꿔.
이런 방법도 가능은 하지만 비효율적이다. 만약 나중에 방금 바꾼 원소의 근처에 있는 것을 바꾸려면 다시 처음부터 시작해야 한다.
이 장에서는 어떤 자료 구조가 있을 때 부분에만 초점(focus)을 맞춰서 원소를 쉽게 바꾸고 효율적으로 탐색하는 방법을 알아본다.
그냥 무작정 걸어가기
아래와 같은 나무 타입이 있다고 하자.
data Tree a = Empty
| Node a (Tree a) (Tree a)
deriving Show나무 타입은 비어 있는 값이거나, 원소 하나와 하위 나무(sub-tree) 두 개를 가지고 있는 노드(node)인 값이다. 아래는 나무 타입 값의 예시이다.
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)
)
)이 나무를 그림으로 표현하면 다음과 같다.
'W'를 'P'로 바꿔 보자. 아래처럼 무식하게 패턴 매칭을 하는 방법이 있다.
changeToP :: Tree Char -> Tree Char
changeToP (Node x l (Node y (Node _ m n) r)) =
Node x l (Node y (Node 'P' m n) r)이 방법은 코드를 읽기도 어렵고 내용도 헷갈릴 수 있다. 패턴 매칭을 이용해서 원소의 이름을 x로 한다. 여기서는 뿌리 자리에 있는 'P'가 된다. 왼쪽 하위 나무는 l이라 한다. 오른쪽 하위 나무는 이름을 따로 주지는 않고 'W'를 만날 때까지 계속해서 패턴 매칭을 한다. 'W'를 만나면 나무를 처음부터 다시 만드는데 'W'가 들어 있던 하위 나무만 'P'로 바꾸면 된다.
다음 방법은 인자로 나무와 함께 방향을 나타내는 값의 리스트를 받는 것이다. 방향을 나타내는 값은 L이거나 R로 각각 왼쪽과 오른쪽을 의미한다.
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방향 리스트의 첫 번째 원소가 L이면 왼쪽 하위 나무만 원소를 'P'로 바꾼 점만 다르고 나머지는 전과 같은 새 나무를 만든다. 왼쪽 하위 나무는 이미 다뤘기 때문에 함수 changeToP를 재귀적으로 호출할 때 방향 리스트의 꼬리(tail)만 인자로 넘긴다. 리스트에서 꼬리란 첫 번째 원소를 제외한 나머지 부분을 말한다. R의 경우에도 같은 방식으로 한다. 방향 리스트가 비었다면 목적지에 도착했다는 것을 의미하므로 뿌리 원소를 'P'로 바꾸기만 하면 된다.
매번 전체 나무를 출력하는 건 번거로우니 아래처럼 인자로 방향 리스트와 나무를 넣으면 목적지에 있는 원소가 나오는 함수를 만들어 보자.
elemAt :: Directions -> Tree a -> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _) = x함수 changeToP는 가는 길을 다 기억했다가 나무를 새로 만들지만 함수 elemAt은 그렇게 하지 않고 목적지만 빼고 나머지는 다 버린다. 아래처럼 'W'를 'P'로 바꿔 보고 잘 바뀌었는지 확인해 보자.
ghci> newTree = changeToP [R,L] freeTree
ghci> elemAt [R,L] newTree
'P'잘 되는 것 같다. 위 함수들에서 방향 리스트는 전체 나무에서 딱 필요한 하위 나무 하나만 골라 주는, 일종의 초점을 맞추는 역할을 한다. 예를 들어 방향 리스트 [R]은 뿌리의 오른쪽 하위 나무에 초점을 맞춘다. 비어 있는 방향 리스트는 전체 나무인 자기 자신에 초점을 맟춘다.
이 방법이 괜찮아 보이기는 하지만 나무나 방향 리스트의 크기가 크고 원소를 반복적으로 바꿀 경우에는 효율적이지 않을 수 있다.
빵 부스러기 따라가기
뿌리에서 출발해서 왼쪽이나 오른쪽을 선택할 때마다 빵 부스러기 같은 것을 남기는 방법은 어떨까? 앞에서 사용했던 타입 Directions를 다시 사용하되 이름만 Breadcrumbs로 바꾸자.
type Breadcrumbs = [Direction]함수 goLeft는 인자로 나무 하나와 빵 부스러기를 받고 왼쪽 하위 나무로 이동한다. 이때 빵 부스러기 리스트 앞에 L을 추가한다.
goLeft :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goLeft (Node _ l _, bs) = (l, L:bs)뿌리에 있는 원소와 오른쪽 하위 나무는 무시한다. 왼쪽 하위 나무와 입력 받은 빵 부스러기 리스트 앞에 L을 붙인 값을 리턴한다. 함수 goRight는 다음과 같다.
goRight :: (Tree a, Breadcrumbs) -> (Tree a, Breadcrumbs)
goRight (Node _ _ r, bs) = (r, R:bs)함수 goRight도 goLeft와 같은 방식으로 동작한다. 제대로 되는지 확인해 보자.
ghci> goLeft (goRight (freeTree, []))
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])
편의를 위해서 아래와 같은 연산자 -:를 정의할 수 있다.
x -: f = f x함수와 인자의 순서를 바꿔서 쓸 수 있는 연산자이다. 이제 goRight (freeTree, [])라고 적는 대신에 (freeTree, []) -: goRight로 쓸 수 있다.
ghci> (freeTree, []) -: goRight -: goLeft
(Node 'W' (Node 'C' Empty Empty) (Node 'R' Empty Empty),[L,R])거꾸로 돌아가기
다시 나무 위로 올라가려면 어떻게 해야 할까? 빵 부스러기를 보면 여기까지 온 경로를 알 수 있다. 현재 나무는 그 전 나무의 왼쪽 하위 나무이고 그 전 나무는 전전(?) 나무의 오른쪽 하위 나무인 것을 알 수 있다. 그런데 이렇게 지나온 경로 말고 다른 정보는 없기 때문에 다시 돌아가기는 어렵다. 빵 부스러기에는 방향 뿐만 아니라 지나온 나무에 대한 정보도 있어야 할 것 같다.
빵 부스러기 하나는 부모 노드를 다시 만들기 위해서 필요한 정보를 모두 가지고 있어야 한다. 그러려면 여기까지 오면서 들르지 않았던 길의 정보와 방향을 모두 알아야 한다. 이때 빵 부스러기에 현재 선택한 하위 나무에 대한 정보를 포함할 필요는 없다.
빵 부스러기가 지나온 길에 대한 정보를 모두 포함하도록 새로운 타입을 만들어 보자.
data Crumb a = LeftCrumb a (Tree a)
| RightCrumb a (Tree a)
deriving (Show)생성자 LeftCrumb는 이제 그냥 방향을 나타내는 L만 있는 게 아니라 거쳐온 길의 원소와 가지 않은 오른쪽 나무에 대한 정보도 있다. RightCrumb도 같은 방식이다.
이제 모든 빵 부스러기는 구멍이 하나씩 뚫린 하나의 나무와도 같게 되었다. 나무 아래로 깊게 내려갈 수록 빵 부스러기는 현재 선택한 하위 나무를 제외하고 우리가 거쳐온 모든 길에 대한 정보를 담게 된다.
타입 별명 Breadcrumbs도 다음과 같이 변경하자.
type Breadcrumbs a = [Crumb a]함수 goLeft와 goRight도 이동하면서 선택하지 않았던 길에 대한 정보를 빵 부스러기에 담도록 변경해야 한다.
goLeft :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goLeft (Node x l r, bs) = (l, LeftCrumb x r:bs)전에 만들었던 goLeft와 비슷하지만 빵 부스러기 리스트에 L만 더하는 게 아니라 LeftCrumb를 더하면서 왼쪽으로 이동했다는 사실을 표시하고 거쳐온 길의 원소와 선택하지 않은 오른쪽 하위 나무에 대한 정보도 같이 담는다.
이 함수는 현재 선택한 나무가 Empty가 아니라고 가정한다. 빈 나무는 아무 하위 나무도 없기 때문이다. 빈 나무에서 왼쪽으로 가려고 시도하면 에러가 난다.
함수 goRight도 비슷하다.
goRight :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goRight (Node x l r, bs) = (r, RightCrumb x l:bs)전에는 왼쪽 오른쪽으로만 갈 수 있었지만 이제 거쳐온 길과 가지 않은 길을 모두 알기 때문에 위로 올라갈 수도 있다.
goUp :: (Tree a, Breadcrumbs a) -> (Tree a, Breadcrumbs a)
goUp (t, LeftCrumb x r:bs) = (Node x t r, bs)
goUp (t, RightCrumb x l:bs) = (Node x l t, bs)현재 나무 t에 초점을 맞추고 있고 가장 최근 빵 부스러기가 뭔지 확인한다. 가장 최근 빵 부스러기는 LeftCrumb이니까 나무 t가 왼쪽 하위 나무인 새로운 나무를 만든다. 가지 않았던 오른쪽 하위 나무와 원소의 정보도 Node에 추가한다. 이제 초점을 옮겼으니 현재 나무에 대한 정보는 빵 부스러기에서 제외한다.
만약 현재 초점을 맞춘 나무가 제일 꼭대기라면 위로 올라가려고 할 때 에러가 난다. 초점을 옮길 때 실패할 가능성은 나중에 Maybe 모나드로 표현하자.
Tree a와 Breadcrumbs a 순서쌍으로 전체 나무를 재구성할 수 있는 모든 정보를 표현할 수 있고 특정 하위 나무에 초점을 맞출 수 있게 되었다. 이 방식을 이용하면 위쪽, 왼쪽, 오른쪽으로 쉽게 이동하는 것도 가능하다. 이렇게 자료 구조의 부분과 그 주변을 포함하는 순서쌍을 지퍼(zipper)라고 부르는데 초점을 위아래로 이동하는 모습이 바지의 지퍼를 올리고 내리는 것과 비슷하기 때문이다. 다음과 같이 타입 별명을 지을 수 있다.
type Zipper a = (Tree a, Breadcrumbs a)초점 맞춘 상태에서 나무 바꾸기
이제 위아래로 이동할 수 있다. 지퍼로 초점을 맞춘 하위 나무의 뿌리에 있는 원소를 변경하는 함수를 만들어 보자.
modify :: (a -> a) -> Zipper a -> Zipper a
modify f (Node x l r, bs) = (Node (f x) l r, bs)
modify _ (Empty, bs) = (Empty, bs)입력으로 노드가 들어오면 원소를 함수 f로 바꾼다. 빈 나무가 들어오면 그냥 그대로 둔다.
ghci> newFocus = (freeTree,[]) -: goLeft -: goRight -: modify (\_ -> 'P')ghci> newFocus2 = newFocus -: goUp -: modify (\_ -> 'X')빵 부스러기에는 가지 않았던 길이 저장되어 있는데 순서가 원래 나무와는 반대로 거꾸로이다. 그래서 뿌리부터 찾아갈 필요 없이 하나씩 꺼내서 초점을 맞추면 된다.
각 노드는 하위 나무가 두 개씩 있는데 하위 나무는 빈 나무일 수 있다. 만약 이 빈 나무에 초점을 맞추게 되면 비어 있지 않은 나무를 더해줘야 하는데 아래 함수를 이용한다.
attach :: Tree a -> Zipper a -> Zipper a
attach t (_, bs) = (t, bs)ghci> farLeft = (freeTree,[]) -: goLeft -: goLeft -: goLeft -: goLeft
ghci> newFocus = farLeft -: attach (Node 'Z' Empty Empty)맨 꼭대기로 올라가기
topMost :: Zipper a -> Zipper a
topMost (t,[]) = (t,[])
topMost z = topMost (goUp z)참고
