読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

Clojureにおけるデータ構造の抽象化を理解して独自のデータ構造を実装する Part 3: 独自Vector作成をマクロ化してみる

さて、前回までで独自のVectorを定義することはできるようになったので、これをまとめてみよう。方針としては、Part1で作成した半端なVectorクラスに、SeqableインターフェースとReversibleインターフェースを実装すれば完成だ。

ひとまず完全なvector実装

;; derefできるオブジェクトかどうか?の簡易な判定
(defn- derefable? [val]
  (or (future? val)
      (delay? val)
      (instance? clojure.lang.Ref val)
      (instance? clojure.lang.Atom val)
      (instance? clojure.lang.Agent val)))

;; これから定義する MyVec type
(deftype MyVec [contents]
  clojure.lang.Associative
  (entryAt [_ key]
    (let [v (.entryAt contents key)]
      (if (derefable? v)
        @v
        v)))
  (assoc [_ key val]
    (MyVec. (.assoc contents key val)))

  clojure.lang.IPersistentStack
  (peek [_] (.peek contents))
  (pop [_] (MyVec. (.pop contents)))

  clojure.lang.Reversible
  (rseq [_]
    (.rseq contents)) ;; Todo
  
  clojure.lang.Indexed
  (nth [_ i]
    (let [v (.nth contents i)]
      (if (derefable? v) @v v)))
  (nth [_ i not-found]
    (let [v (.nth contents i not-found)]
      (if (derefable? v) @v v)))

  clojure.lang.IPersistentCollection
  (count [_]
    (.count contents))
  (empty [_]
    (.empty contents))
  (equiv [_ o]
    (and (isa? (class o) MyVec)
         (.equiv contents (:contents o))))

  clojure.lang.ILookup
  (valAt [_ k]
    (let [v (.valAt contents k)]
      (if (derefable? v)
        @v
        v)))
  (valAt [_ k not-found]
    (let [v (.valAt contents k not-found)]
      (if (derefable? v)
        @v
        v)))

  clojure.lang.IPersistentVector
  (assocN [_ i val]
    (MyVec. (.assocN contents i val)))
  (cons [_ o]
    (MyVec. (.cons contents o)))

  clojure.lang.Sequential
  clojure.lang.Seqable
  (seq [this]
    (letfn [(seq' [idx] (if (>= idx (count contents))
                        nil
                        (cons (.nth this idx)
                              (lazy-seq (seq' (inc idx))))))]
      (seq' 0)))

  clojure.lang.Reversible
  (rseq [this]
    (letfn [(rseq' [idx] (if (< idx 0)
                           nil
                           (cons (.nth this idx)
                                 (lazy-seq (rseq' (dec idx))))))]
      (rseq' (dec (count this))))))



;;; 使用してみる
=> (let [v (MyVec. [1 2 3 (delay (heavy-computation 4)) (atom 5)])]
                (nth v 3))
4

=> (let [v (MyVec. [1 2 3 (delay (heavy-computation 4)) (atom 5)])]
                (rseq v))
(1 2 3 4 5)

=> (let [v (MyVec. [1 2 3 (delay (heavy-computation 4)) (atom 5)])]
                (rseq v))
(5 4 3 2 1)

ちゃんと動作しているようだ。

マクロ化する

さて、上記のdeftypeは、いろいろと問題が多いことは明らかだ。

  1. 長い&インターフェースが多い。メソッド名はともかく、インターフェースとメソッド名の対応を覚えておく必要がある
  2. 重複が多い。vectorを定義するという前提なら、clojure.lang.Associative#entryAtclojure.lang.Indexed#nthclojure.lang.ILookup#valAtの3つの関数は同内容となるだろう。同じ事を3カ所にかかなければならず煩雑だ。

もちろん、Clojureプログラマーはこのようなときマクロを使うのである。マクロの実装は customcoll/vector.clj at master · keisukefukuda/customcoll · GitHub に定義してある。このdefcustomvecマクロを使うと、上のコードは以下のように書ける。(実は、2引数nthと3引数nthを何とか共通化できないかどうか検討中)。

(defcustomvec MyVec [contents]
  (nth [this i]
       (let [v (nth contents i)]
         (if (derefable? v) @v v)))
  (nth [this i not-found]
       (let [v (nth contents i not-found)]
         (if (derefable? v) @v v))))


=> (let [v (MyVec. [1 2 (future 3) (atom 4) (delay 5)])]
                          (seq v))
(1 2 3 4 5)

=> (let [v (MyVec. [1 2 (future 3) (atom 4) (delay 5)])]
                          (rseq v))
(5 4 3 2 1)

おもしろいVectorを定義してみる

このライブラリを使うと、例えば負のインデックスを許容するvectorなども作れる。

;; 最初の要素のindexがbaseであるようなvector
(defcustomvec ShiftRangeVector [contents base]
  (nth [_ i]
       (.nth contents (- i base)))
  (nth [_ i not-found]
       (.nth contents (- i base) not-found))
  (assoc [_ i v]
         (ShiftRangeVector. (.assoc contents (- i base) v) base))
  (seq [this]
       (.seq contents))
  (rseq [this]
        (.rseq contents)))


;; 使用例

=> (let [v (ShiftRangeVector. [1 2 3] -1)]
                          (nth v -1))
1

=> (let [v (ShiftRangeVector. [1 2 3] -1)]
                          (nth v 0))
2

=> (let [v (ShiftRangeVector. [1 2 3] -1)]
                          (seq v))
(1 2 3)

この実装は、将来ライブラリとしてリリースする予定。map, setにも対応して、ClojureScriptも同様にできるようにしたい。次回は、ClojureScriptの内部実装を見てみたい(ちょっと遅くなるかもしれません)。

【広告】