Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2008-11-23

CLとデザインパターン - Iterator

| 20:24 | CLとデザインパターン - Iterator - わだばLisperになる を含むブックマーク はてなブックマーク - CLとデザインパターン - Iterator - わだばLisperになる

今回はIteratorパターンです。

Iteratorパターンは、理解しやすいということで入門書籍のトップになることが多いらしいのですが、Norvig氏のIteraton Protocolの提案(Dylanで実現)等があるので、この辺を押えてから纏めたいなと思っていました。

しかし、纏められそうもないのでとりあえず簡単なパターンを演習してみることにしました。

ちなみに、Greg Sullivan氏のGOF Design Patterns in a Dynamic OO Languageによればファースト・クラスの関数と内部イテレータの組み合わせ(map、dolist等)は非常に柔軟で応用範囲も広い、とのことなのですが、デザインパターンは外部イテレータのようなのでそれで行くことにしました。

基本的に、現在位置のアイテムを取得する、CurrentItem、位置をリセットするFirst、終わりかどうかを判定する、IsDone、次に進めるNextがあればOKのようで、これらを応用したものが色々あるようです。

今回は、平坦な構造(ベクタや、リスト)を先頭から見て行くことしか考慮してませんが、ツリー構造等もmake-iteratorの方を工夫すればどうにかなるのでしょう。

(defclass iterator () 
  ((obj :initform () :initarg :obj)
   (index :initform 0)
   (size :initform 0)
   (accessor :initform #'elt :initarg :accessor)))

(defmethod initialize-instance :after ((iter iterator) &key)
  (with-slots ((obj obj) (size size)) iter
    (setf size (length obj))))

(defgeneric make-iterator (obj)
  (:method (obj) 
    (make-instance 'iterator :obj obj)))

(defmethod make-iterator ((obj list))
  (make-instance 'iterator :obj obj 
                 :accessor (lambda (obj index)
                             (nth index obj))))

(defmethod make-iterator ((obj vector))
  (make-instance 'iterator :obj obj :accessor #'aref))

;; iterator関数群
(defgeneric first! (iter)
  (:method ((iter iterator))
    (setf (slot-value iter 'index) 0)))

(defgeneric next! (iter)
  (:method ((iter iterator))
    (incf (slot-value iter 'index))))

(defgeneric done? (iter)
  (:method ((iter iterator))
    (with-slots ((index index) (size size)) iter
      (>= index size))))

(defgeneric current-item (iter)
  (:method ((iter iterator))
    (with-slots ((obj obj) 
                 (index index)
                 (accessor accessor)) iter
      (funcall accessor obj index))))

;; 動作
(do ((iter (make-iterator '(1 2 3 4)))
     ans)
    ((done? iter) ans)
  (push (current-item iter) ans)
  (next! iter))

;; 面倒臭いのでマクロ定義/イテレータ定義は外に出した方が良いかも
(defmacro doiter ((var iter &optional result) &body body)
  (let ((g (gensym)))
    `(do ((,g (make-iterator ,iter)))
         ((done? ,g) (let (,var) ,result))
       (let ((,var (current-item ,g)))
         ,@body
         (next! ,g)))))

(doiter (i '(1 2 3 4))
  (print i))

(doiter (i #(a c d e))
  (print i))

(doiter (i "abcde")
  (print i))
;-> #\a 
    #\b 
    #\c 
    #\d 
    #\e 
;=> nil

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20081123