[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Missing and desired sequence function.



I agree with you that this is a useful feature that is an obvious hole in
Common Lisp's sequence functions.  As evidence that it's obviously needed, I
thought of it six weeks ago independently (or did you see my suggestion to
Symbolics Customer Reports, referenced above?).

Below is the implementation I used.  It's an iterative approach using the MIT
LOOP macro, made ugly by the need to handle lists and vectors separately.
It's not as elegant as using SORT or REDUCE, but later I realized I wanted it
to return the position as well as the element; see below.

					--Kanef

(defun minimize (sequence &key (key 'identity) (test '<))
  ;;A generalization of MIN that takes :KEY and :TEST arguments
  ;;as other Common-Lisp functions do.
  ;;Examples:   (minimize '(1 2 3 4)) is the same as (min 1 2 3 4) but slower.
  ;;		(minimize *people* :key 'height) finds the shortest person.
  ;;		(minimize *people* :key 'age) finds the youngest person.
  ;;		(minimize *people* :key 'age :test '>) finds the oldest person.
  (declare (values element position key-value))
  (macrolet ((doit (type)
	       ;;I know the Symbolics implementations of the other sequence functions use a macro
	       ;;for this called CLI::SEQUENCE-ITERATOR, but the callers of it are all in a restricted
	       ;;source.  This macro is the same idea.
	       (let ((iterator (case type
				 (list '(in))
				 (vector '(being the array-elements of)))))
		 `(loop with best-candidate = (elt sequence 0)
			with best-offer = (funcall key best-candidate)
			with best-index = 0
			for index from 0
			for candidate ,@iterator sequence
			for offer = (funcall key candidate)
			when (funcall test offer best-offer)
			  do (setq best-candidate candidate
				   best-offer offer
				   best-index index)
			finally (return (values best-candidate best-index best-offer))))))
    (etypecase sequence
      (list (doit list))
      (vector (doit vector)))))

As soon as I went back to writing the caller of the MINIMIZE function, I
realized that it would be convenient to have it return the index as well as
the element (ala POSITION as well as FIND).

(defun minimize (sequence &key (key 'identity) (test '<))
  ;;A generalization of MIN that takes :KEY and :TEST arguments
  ;;as other Common-Lisp functions do.
  ;;Examples:   (minimize '(1 2 3 4)) is the same as (min 1 2 3 4) but slower.
  ;;		(minimize *people* :key 'height) finds the shortest person.
  ;;		(minimize *people* :key 'age) finds the youngest person.
  ;;		(minimize *people* :key 'age :test '>) finds the oldest person.
  (declare (values element position key-value))
  (macrolet ((doit (type)
	       ;;I know the Symbolics implementations of the other sequence functions use a macro
	       ;;for this called CLI::SEQUENCE-ITERATOR, but the callers of it are all in a restricted
	       ;;source.  This macro is the same idea.
	       (let ((iterator (case type
				 (list '(in))
				 (vector '(being the array-elements of)))))
		 `(loop with best-candidate = (elt sequence 0)
			with best-offer = (funcall key best-candidate)
			with best-index = 0
			for index from 0
			for candidate ,@iterator sequence
			for offer = (funcall key candidate)
			when (funcall test offer best-offer)
			  do (setq best-candidate candidate
				   best-offer offer
				   best-index index)
			finally (return (values best-candidate best-index best-offer))))))
    (etypecase sequence
      (list (doit list))
      (vector (doit vector)))))