iterateパッケージ
Wikipediaのcommon lispの項目を読んでいたら、iterateというパッケージの存在を知った。
少し興味を引かれたのでマニュアルに(簡単に)目を通してみた。
名前の通り、繰り返し処理を行うためのパッケージで、立ち位置的にはloopマクロに近いようだ。
>(iter (FOR i FROM 1 TO 10) (COLLECT i)) --> (1 2 3 4 5 6 7 8 9 10)
ただ、loopとは異なり拡張が可能とのこと。
せっかくなので(?)、試してみる。
拡張
どんな拡張にしようか少し悩んだが、以前、ハフマン木を作成する関数を書いた際に、ヒープに対する(ポップ操作の)繰り返しをdoを使って実装していたことを思い出したので、それをiterateを使って置き換えてみることにした。
以前のハフマン木云々に関してはこっちを参照。
拡張用の関数・マクロはいくつか用意されているようだが、今回はFORフォーム(?)に新しい節を追加するための、defmacro-driverというマクロを使った。
以下が拡張を定義したコードだが、引数の中身が若干異なること以外は、ほとんど普通のマクロと同じ感覚で書くことができた。
(require :iterate) (use-package :iterate) ;; (iter (FOR ... POP-FROM ... PACKAGE ...) ※ PACKAGE節はオプショナル ;; (.....)) (defmacro-driver (FOR var POP-FROM container &optional PACKAGE (pack common-lisp:*package*)) (declare (ignorable generate)) ; defmacro-driverマクロが自動で用意している変数 (let* ((pop (find-symbol "POP" pack)) ; packパッケージから'POPシンボルを探す(繰り返し用) (next-exp (if (consp var) `(loop REPEAT ,(length var) COLLECT (,pop ,container)) `(,pop ,container)))) (assert pop () "symbol POP not found in the ~A package" (package-name pack)) `(for ,var next ,next-exp)))
使い方:
> (defvar *list* '(1 2 3 4 5 6)) ;; リストが空になるまで、要素を取り出す: (pop *list*)が毎回呼ばれる > (iter (FOR x POP-FROM *list*) (COLLECT x) (UNTIL (null *list*))) --> '(1 2 3 4 5 6) ;; 副作用あり > *list* --> NIL > (setf *list* '(1 2 3 4 5 6)) ;; リストが空になるまで、2つずつ要素をpopする > (iter (FOR (x y) POP-FROM *list*) (COLLECT x) (UNTIL (null *list*))) --> '(1 3 5)
リストに対して使う分には、副作用があることを除けば、ほとんど初めからある(FOR ... IN ...)構文と変わらない。
リスト以外の(スタックやキュー的な動作をする)コンテナに適用する場合は、繰り返し中に使用されるpop関数を含むパッケージを、PACKAGE節で指定すれば良い*1。※ common-lisp:*package*にcommon-lispパッケージがバインドされている場合
ハフマン木作成
これを、ハフマン木作成関数に適用してみる。
まず、もともとの関数:
;; ハフマン木を作成 (defun make-huffman-tree (freq-map) (let ((hp (heap:make-heap :test #'freq<))) ;; 1] 初期heap作成 (maphash (lambda (char freq) (heap:push (make-node freq char) hp)) freq-map) ;; 2] heapが空になるまで、「頻度最小の二つのnodeを取り出し、併合して、heapに戻す」という操作を繰り返す (do ((node #1=(heap:pop hp) #1#)) ((heap:empty? hp) node) ; heapに最後に残ったnodeがハフマン木 (let ((node2 (heap:pop hp))) (heap:push (make-node (freq+ node node2) (cons node node2)) hp)))))
この2の部分を、上で作成した(FOR ... POP-FROM ...)ルーブで置き換える。
※ ついでに、1の部分もiterateを使うように修正してある。
修正後の関数:
(defun make-huffman-tree (freq-map) (let ((hp (heap:make-heap :test #'freq<))) ;; 1] 初期heap作成 (iter (FOR (char freq) IN-HASHTABLE freq-map) (heap:push (make-node freq char) hp)) ;; 2] heapが空になるまで、「頻度最小の二つのnodeを取り出し、併合して、heapに戻す」という操作を繰り返す ;; XXX: ヒープの要素数が2未満の場合にはエラーとなる ※1 (iter (FOR (1st 2nd) POP-FROM hp PACKAGE :heap) ; <- heap:pop関数を使って要素を取り出す (FOR merged-node = (make-node (freq+ 1st 2nd) (cons 1st 2nd))) (when (heap:empty? hp) (leave merged-node)) (heap:push merged-node hp)))) ;; ※1 修正版: 若干分かりにくい ;;(iter (FOR (1st 2nd) POP-FROM hp PACKAGE :heap) ;; (when (null 2nd) ;; (leave 1st)) ;; (heap:push (make-node (freq+ 1st 2nd) (cons 1st 2nd)) hp))
行数は多くなってしまった*2が、doを使ったものよりは、分かりやすくなったと思う。
###
今回の拡張が使えるかどうかはともかく、(普通のマクロを書くくらい)簡単に独自の繰り返し処理を定義できるのはいいと思う。
標準の制御構造を使ったり、似たようなマクロを書くことも難しくはないが、iterateパッケージを使った方がシンタックスが統一できるし、基盤が既にあるので新たに作成する労力も少なくて済む。
まあ、依存パッケージが増えるというのが(個人的には)デメリットなので、常用することはないと思うが、いろいろ試してみるのは良いかもしれない。
※ それはそうと、clsqlではcommon lispのloopを拡張してるっぽいのだが、どうやってやっているのだろう?