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

find-min/find-max

common lisp utility

列の要素にキー関数を適用して、その結果が最大(or 最小)となる要素を返す、という関数。
loopマクロのmin/max辺りでやってくれるかなと思ったが、無理そうなので自作した。
マクロをふんだんに使用。

(defmacro find-xxx-helper (empty? first loop compare key-fn seq)
  `(if (,empty? ,seq)
       nil
     ;; 最初の要素とその値(key-fn適用結果)を取得
     (let* ((top-elem  (,first ,seq))
            (top-value (funcall ,key-fn top-elem)))
      ;; 二番目以降の要素に対するループ 
      (,@loop
        (let ((value (funcall ,key-fn elem))) 
          (when (,compare value top-value) ;; top-elemの値と比較
            (setf top-elem elem            ;; top-xxx更新
                  top-value value))))
       (values top-elem top-value))))

(defmacro find-xxx (compare key-fn seq)
  (let ((list-loop '(dolist (elem (cdr seq))))
        (vector-loop '(loop for i from 1 below (length seq) 
                            for elem = (aref seq i) do))
        (#1=vector-empty? '(lambda (v) (zerop (length v))))
        (#2=vector-first  '(lambda (v) (aref v 0))))

    `(etypecase ,seq
       (list   (find-xxx-helper null car  ,list-loop   ,compare ,key-fn ,seq))
       (vector (find-xxx-helper ,#1# ,#2# ,vector-loop ,compare ,key-fn ,seq)))))

;; 列の各要素にkey-fnを適用して、その値が最小/最大となった要素を返す
;;  値が最小/最大となる要素が複数ある場合は、その内の最初のものが返される => TODO: :from-endフラグをつける?
;; 返り値は、(values 最小/最大要素 key-fnの適用結果)となる
;; ただし、渡されたseqが空の場合は、nilを返す
(defun find-min (key-fn seq) (find-xxx < key-fn seq))
(defun find-max (key-fn seq) (find-xxx > key-fn seq))

使用例:

> (find-min #'second '((:a 10) (:b 30) (:c 2) (:d 5)))
--> (:C 2)
    2

> (find-max #'char-code "列の各要素にkey-fnを適用して、その値が最小/最大となった要素を返す")
--> #\U9069  ; #\適
    36969

> (find-min #'char-code "")
--> NIL