zipperについて

Clojureではネストしたデータ構造を頻繁に扱います。例えば、

[1 2 [:a [3] :b] :c]

のように、ベクトルの要素がベクトルになっているものや、

{:a 1 :b {:c 2 :d {:e 3}}}

のようにマップの要素が再びマップになっているものです。このようなネストしたデータ構造を扱う際に便利なライブラリーとしてclojure.zipがあります。この記事では、zipの基本的な使用方法について解説しています。

準備

clojure.zipはClojureに標準装備されています。よって、外部からのインストールは必要なく、ソースファイルに以下の記述を加えるだけで利用できます。

(ns main.core
  (:require [clojure.zip :as z]))

locとnode

zipを理解する上で重要な概念として、locとnodeがあります。ここでは説明のために、以下のように定義されるネストしたベクトルnested-vectorを扱います。

(def nested-vector [1 2 [:a [3] :b] :c])

ネストしたベクトルを探索する場合には、まず、z/vector-zipにより「ルート」を取得します。

(z/vector-zip nested-vector)
=> [[1 2 [:a [3] :b] :c] nil]

このようにして取得された「ルート」に対して、z/nextを繰り返し適合することでネストしたベクトルの深さ優先探索が行えます。例えば、nested-vectorにおいて2という要素は、ルートから2番目の位置にありますから、そこにアクセスするにはz/nextを2回適用すればいいでしょう。

(let [root (z/vector-zip nested-vector)]
  (-> root z/next z/next))

=> [2  {:l [1],
        :pnodes [[1 2 [:a [3] :b] :c]],
        :ppath nil
	:r ([:a [3] :b] :c)}]

少し複雑な結果になりました。実は、clojure.zipでは、各要素(node)に到達するまでの道筋などの情報を保存していて,z/nextなどの関数は、そのような情報を帰り値のベクトルの2番目の要素に格納しています。このように

[node　nodeに関する情報]

という形のデータをclojure.zipではlocと呼んでいます。locから値を取り出したい場合は、z/nodeを使います。

(let [root (z/vector-zip nested-vector)]
  (-> root z/next z/next z/node))

=> 2

通常、locの2番目の要素(:lや:pnodesなどのキーを含むマップ）を直接操作することはありません。（むしろ止めた方が良い）

しかし、後ほど登場するz/nextなどの関数はlocを引数に取ります。

clojure.zipによる深さ優先探索の視覚化

locにz/nextを適用すると、ネストしたデータの深さ優先探索における次のlocが返されます。z/nextがどのようにnested-vectorの要素を探索していくか、表示したものが下図になります。

この図では、深さ優先探索で同じ深さの要素の集合を四角で囲っています。また、矢印はz/nextを繰り返しlocに適応していった時に探索される要素の順番を示しています。

clojure.zipは深さ優先探索を行うので、ベクトルの要素でありながらかつ自身がベクトルであるといった「親ノード」に来た時点で、その「親ノード」の子要素を探索しているのが分かります。

全ての要素を集める

clojure.zipの活用例として、上で定めたnested-vectorの全ての要素を集めるということを考えます。

z/nextを繰り返し適用していけば、いつかは深さ優先探索の終点に到達します。z/end?は、最後のlocを渡すとtrueを返す関数です。つまり、z/nextを繰り返し使うことで深さ優先探索を行う場合、z/end?によりループの終了条件とすることができます。

以上に注意し、ネストしたベクトルの全ての要素を取り出す関数を作成します。

(defn collect-items
  [v]
  (loop [acc [], loc (z/vector-zip v)]
    (if (z/end? loc)
      acc
      (recur (conj acc (z/node loc)) (z/next loc)))))

(collect-items nested-vector)
=>
([1 2 [:a [3] :b] :c]
1
2
[:a [3] :b]
:a
[3]
3
:b
:c)

ちなみに、同じ結果を出す関数をloopなしで作ることもできます。

(defn collect-items-functional [v]
  (map z/node
       (take-while
        (complement z/end?)
        (iterate z/next (z/vector-zip v)))))

こちらの方がより「関数型プログラミング」の意向に適ったものと言えるかもしれません。

要素の編集

clojure.zipには、データの要素を編集するための関数も用意されています。それが、z/editです。
z/editは

(e/edit loc f & args)

というシグネチャをもち、locのnodeの値を

(f node & args)

の帰り値によって置き換えます。

以下では、例として、nested-vectorのキーワードの要素を全て文字列に置き換える関数を作成してみます。

このような関数をloopによって作る場合、探索が最後のlocに到達した時に変更されたデータを返す必要があります。このために使用するのが、z/rootです。z/rootは任意のlocを引数にとり、探索の開始地点のnodeを返す関数です。さらに、z/editなどによって行われた変更を全て反映します。

(defn keyword->string [v]
  (loop [loc (z/vector-zip v)]
    (if (z/end? loc)
      (z/root loc)
      (let [node (z/node loc)]
        (if (keyword? node)
          (recur (z/next (z/edit loc str)))
          (recur (z/next loc)))))))

(keyword->string nested-vector)
=> [1 2 [":a" [3] ":b"] ":c"]

ここでの注意点は、キーワードかどうかの判定に用いる関数keyword?を、locではなくnodeに適用しているということです。先述したように、z/nextは[node map]という形のベクトル(loc)を返すので、これにnodeに対する関数を適用するのは誤りになります。

要素の削除

keyword->stringのように、loopとzipperの関数を組み合わせる手法を理解すれば、ネストしたデータの中の特定の要素を削除する関数を作成するのも難しくはありません。例として、ネストしたベクトルを引数とし、キーワードの要素のみを削除する関数を作成してみましょう。

(defn erase-keyword [v]
  (loop [loc (z/vector-zip v)]
    (if (z/end? loc)
      (z/root loc)
      (let [node (z/node loc)]
        (if (keyword? node)
          (recur (z/next (z/remove loc)))
          (recur (z/next loc)))))))

(erase-keyword nested-vector)
 => [1 2 [[3]]]

zipperのカスタマイズ

これまで見てきたように、clojure.zipではネストしたデータを深さ優先探索することで、要素の収集、編集、削除と言った操作を行うことができます。

clojure.zipには

z/seq-zip
z/vector-zip
z/xml-zip

のように、頻繁に用いるzipperが用意されているので、これらに適合するデータを扱う場合には、特に問題はありません。しかし、これらに適合しないデータを探索しようとする時は、自分でzipperを作る必要があります。

例として、以下のようにネストしたマップを探索することを考えます。

(def nested-map {:a 1 :b {:c {3 :d}} 4 :e})

nested-mapの構造を表示すると、以下のようになります。

このようにネストしたマップを扱う場合、上記のzipperでは探索を行うことができません。その理由を理解するために重要なのが、ブランチノードの定義です。ブランチノードとは、ネストしたデータにおいて、子ノードを持てるようなノードを指します。例えば、前半で扱ったnested-vectorでは、[:a [3] :b]のようなものがブランチノードです。

nested-mapでは、ブランチノードの定義はネストしたベクトルのものとは異なることに注意します。すなわち、「その要素自体がマップであるかどうか」がブランチノードの判定基準となります。ネストしたデータの種類が変われば、それに応じてzipperの種類も変える必要があるということです。

z/zipperにより、カスタマイズされたzipperを作ることが可能です。z/zipperは、

(z/zipper branch? children make-node root)

というシグネチャをしています。これらの意味を詳しく見ていくと、

branch? : nodeを受け取り、そのnodeがブランチである時trueを返す関数

children : nodeを受け取り、そのnodeの子nodeのシーケンスを返す関数

make-node : nodeとchildrenを受け取り、childrenを子ノードとする新しいnodeを返す関数

とあります。実際に、zipperのソースコードでvector-zipの実装を確認してみると

(defn vector-zip
  "Returns a zipper for nested vectors, given a root vector"
  {:added "1.0"}
  [root]
    (zipper vector?
            seq
            (fn [node children] (with-meta (vec children) (meta node)))
            root))

となっていいます。

それでは、nested-mapに対応するzipperを作成してみましょう。

まず、branch?ですが、これはネストしたマップを扱うので、要素自体がマップである時にそれがブランチノードであるということになります。

(defn map-zip-branch? [x] (map? x))

次にchildrenですが、これは、与えられたマップの各要素のkey,valueからなるリストを返すようにします。つまり、

{:a 1 :b 2} -> (:a 1 :b 2)

という変換をします。

(defn map-zip-children [x] (concat (keys x) (vals x)))

最後に、make-nodeですが、これは上のようにkeyとvalueが交互に配列されたリストから逆にマップを作ります。すなわち、

(:a 1 :b 2) -> {:a 1 :b 2}

さらに、vector-zipのように、元のnodeのメタ情報を保存するようにします。

(defn map-zip-make-node [node children]
  (with-meta
    (zipmap (take-nth 2 children) (take-nth 2 (rest children)))
    (meta node)))

以上で、ネストしたマップに適応したzipperに必要な関数が用意されました。これらにより、目的のzipperを作成できます。

(defn map-zip [root]
  (z/zipper map-zip-branch?
            map-zip-children
            map-zip-make-node
            root))

map-zipを使えば、nested-mapの要素の探索が可能となります。実際に、「全てのキーワードを文字列に変換する」という操作をnested-mapにも行ってみましょう。

(defn keyword->string-map [m]
  (loop [loc (map-zip m)]
    (if (z/end? loc)
      (z/root loc)
      (let [node (z/node loc)]
        (if (keyword? node)
          (recur (z/next (z/edit loc str)))
          (recur (z/next loc)))))))

(keyword->string-map nested-map)

=> {":a" ":b", 4 1, {":c" {3 ":d"}} ":e"}

まとめ

この記事では、ネストしたデータを扱うためのライブラリーであるclojure.zipについて解説しました。ネストしたデータの収集や編集、特定の条件を満たすデータの削除の方法などを紹介しました。また、ネストの意味に応じて対応するzipperの作成方法を説明しました。参考にしていただければ幸いです。

参考リンク

API for clojure.zip

clojure.zipのソースコード