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

*To*: common-lisp@sail.stanford.edu*Subject*: Missing and desired sequence function.*From*: Bob Kanefsky <Kanef@SPAR.SLB.COM>*Date*: Wed, 11 Nov 87 22:09 PST*In-reply-to*: <19871111230324.4.DCP@SWAN.SCRC.Symbolics.COM>*References*: <870923091026.7.7THSON@MOTH.SPAR.CAS.SLB.COM>

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)))))

**References**:**Missing and desired sequence function.***From:*David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>

- Prev by Date:
**Re: Local redefs of special forms** - Next by Date:
**Missing and desired sequence function.** - Previous by thread:
**Missing and desired sequence function.** - Next by thread:
**Missing and desired sequence function.** - Index(es):