User Tools

Site Tools


study:algorithms:zipper

Clojure Zipper

Zipper는 트리를 순회하고 편집하기 위한 함수형 방식의 기술이다. 알고리즘 문제에서 트리는 자주 나오므로 Zipper를 알아두면 좋을 것이다. Zipper에 대한 개념은 Huet에 의해 정립되었다.

클로져의 Zipper 구현은 Clojure.zip이다. Clojure.zip을 사용하는 방법은 Brian Marick에 의해 잘 정리되어 있다.

여기서는 Clojure.zip의 구현에 대해 알아볼 것이다.

Zipper 데이타 구조

Clojure.zip의 모든 api들은 Clojure Zipper 데이타 구조에 전적으로 의존한다. 따라서 Zipper 데이타 구조를 이해하는 것이 핵심이다.

location과 path

우선 Zipper에서 사용되는 몇가지 개념에 대해 알아보자.

  • location : zipper의 연산이 수행되는 위치를 일컫는다.
  • path : 연산이 수행되면서 지나쳐온 경로.
  • node : 연산이 수행되는 대상.
  • down : 트리의 하방 이동 (가장 왼쪽의 자식을 리턴한다).
  • up : 트리의 상방 이동 (현재 위치에서의 부모를 리턴한다).
  • left : 왼쪽 형제로 이동.
  • right : 오른쪽 형제로 이동.

Zipper는 마치 DNA 염기 사슬이 묶이거나 풀리듯이 트리의 하방과 상방을 이동하면서 경로 정보를 유지한다. 이것을 path라고 한다. location은 현재의 연산이 수행되는 위치를 가리킨다. (Zipper의 path와 location은 파일시스템의 path와 current directory와 같은 개념이다)

우선 다음 코드를 보자.

(require '[clojure.zip :as z])
;=> nil
(def t (z/vector-zip [[1] [2]]))
;=> #'user/t
t
;=> [[[1] [2]] nil]
(z/down t)
;=> [[1] {:l [], :pnodes [[[1] [2]]], :ppath nil, :r ([2])}]
(z/down (z/down t))
;=> [1 {:l [], :pnodes [[[1] [2]] [1]], :ppath {:l [], :pnodes [[[1] [2]]], :ppath nil, :r ([2])}, :r nil}]

vector-zip 함수는 벡터를 root로 해서 순회/편집하는 Zipper 데이타 구조를 만든다.

Zipper 데이타 구조는 node와 path로 된 튜플이다.

 Zipper 데이타 구조 : [node path]

node는 순회/편집을 위한 데이타 구조로서 location을 말하며, path는 map으로 된 경로 정보이다.

위 코드에서 트리의 하방으로 내려가는 함수인 down을 통해 Zipper 데이타 구조가 변하는 것을 볼 수가 있다.

location node path
t [ [1] [2] ] nil
(down t) [1] {:l [], :pnodes [ [ [1] [2] ] ], :ppath nil, :r ([2])}
(down (down t)) 1 {:l [], :pnodes [ [ [1] [2] ] [1] ], :ppath {:l [], :pnodes [ [ [1] [2] ] ], :ppath nil, :r ([2])}, :r nil}

이런식으로 path가 항상 현재 위치인 location의 왼쪽 형제와 오른쪽 형제 정보와 부모 정보를 가지고 있는데, 다음과 같이 그려볼 수 있다.

   
                    parent1
                       |
                    parent2
                       |
                      ...
                       |
   lefts ㅡ ... ㅡ location  ㅡ ...ㅡ rights

위와 같은 형태로 되어 있는 것이 마치 지퍼를 잠그고 여는 것 같다고 해서 이름이 Zipper인 것이다.

메타데이타

zipper는 vector나 list등의 데이타구조를 순회/편집하는 Zipper 데이타구조를 리턴하는데, 이를 위해 다음의 함수를 인자로 받는다.

  • branch? : 노드가 가지인지 판단하는 함수.
  • children : 해당 노드에서 자식을 구하는 함수.
  • make-node : 해당 노드의 자식을 바꾸는 함수.

위의 코드에서 사용된 vector-zip 함수는 zipper를 사용한 것이다. 다음은 zipper 함수의 정의이다.

(defn zipper
[branch? children make-node root]
    ^{:zip/branch? branch? :zip/children children :zip/make-node make-node}
    [root nil])

zipper 함수는 root를 node로 하고 path는 nil로 하는 Zipper 데이타 구조를 만들어 리턴하는데, 여기에 :zip/branch?와 :zip/children, :zip/make-node를 메타데이타로 추가하고 있다. 결국 Zipper 데이타 구조의 메타데이타는 Zipper 데이타 구조를 처리하기 위한 함수들인 것이다. 그리고 모든 clojure.zip 함수들은 이 메타데이타 유지하는 Zipper 데이타 구조를 리턴한다.

clojure.zip/branch?, clojure.zip/children, clojure.zip/make-node 함수는 이 메타데이타를 이용한다.

(ns clojure.zip ...)
 
(defn branch?
  [loc]
    ((:zip/branch? (meta loc)) (node loc)))
 
(defn children
  [loc]
    (if (branch? loc)
      ((:zip/children (meta loc)) (node loc))
      (throw (Exception. "called children on a leaf node"))))
 
(defn make-node
  [loc node children]
    ((:zip/make-node (meta loc)) node children))

Zipper를 이용한 트리 순회

;;; vector-zip
(defn mz  [root] (z/vector-zip root))
(defn value [loc] (-> loc z/node first))
(defn left  [loc] (-> loc z/down z/right))
(defn right [loc] (-> loc z/down z/right z/right))
(defn node? [loc] (not (nil? loc)))
 
 
(defn walk [node order acc]
  (if (node? node)
    (reduce #(if (= %2 value)
                 (conj %1 (value node))
                 (walk (%2 node) order %1))
            acc 
            order)
    acc))
 
(defn preorder [node]
  (walk (mz node) [value left right] []))
 
(defn inorder [node]
  (walk (mz node) [left value right] []))
 
(defn postorder [node]
  (walk (mz node) [left right value] []))
 
(defn level-order [tree]
  (let [group #(vals (group-by vector? %))]
  (loop [[a b] (group tree) acc []]
    (if (empty? b)
        (concat acc a)
        (recur (group (apply concat b)) (concat acc a))))))
 
(def tree [1 [2 [4 [7]] [5]] [3 [6 [8] [9]]]])
 
(preorder tree)
;=> [1 2 4 7 5 3 6 8 9]
(inorder tree)
;=> [7 4 2 5 1 8 6 9 3]
(postorder tree)
;=> [7 4 5 2 8 9 6 3 1]
(level-order tree)
=> (1 2 3 4 5 6 7 8 9)

Zipper를 이용한 트리 수정

Zipper를 이용한 레코드 트리 수정

Zipper를 이용한 HTML 수정

study/algorithms/zipper.txt · Last modified: 2019/02/04 14:26 (external edit)