[cl-utilities-devel] Another extremum concept

[Gustavo]

One I made a function that I needed that looks like the idea of extrema. I
saw it and tested to see if it did what I thought:

COMMON-LISP-USER>
(cl-utilities:extrema  '((1 2 3) (1 2) (1 3) (2 3) (2 3 4)) #'subsetp)

((1 2) (1 3) (2 3) (2 3 4))


And realized that it doesn't. It returns (2 3 4), and I was assuming that it
wouldn't because (2 4) is strictly smaller (in subset sense). Then I took a
look at the code and realized that it is supposed to do something different
from what I was expecting. The given order is assumed to "total" (given a
equivalence), not "partial" as I thought. In partial order, two elements a,
b that neither a < b and b < a are not assumed equal or equivalent.

Anyway, the function I did (renaming to extremals to be consistent to the
notation, but initially it was named minimals), tested to many cases, is
this:

(defun extremals (seq pred)
  (loop for member on seq
        for elt = (car member)
        unless (or (find-if (rcurry pred elt)
                        (cdr member))
               (find-if (f_ (and (not (eq _ elt))
                                 (funcall pred _ elt)))
                        befores))
          collect elt
          and collect elt into befores))

Where

(defmacro f_ (&body body)
  `(function (lambda (_) , at body)))

(defun rcurry (function &rest args)
  (f_ (apply function _ args)))

Actually I found that really interesting specially to comparing types. E.g.,
if you are dealing with the "and" type specifier, e.g.:

(and integer fixnum)

You might want to remove every type that is more complex such that, in this
case, only the fixnum remains. In this case, something like

(if (eq (car type-spec) 'and)
  (cons 'and (extremals (cdr type-spec) #'subtypep)))

Does the job (and looks quite pretty lisp code :)

Be free to use this code, but just if you want to. I, Gustavo, put it under
public domain.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cl-utilities-devel/attachments/20080311/3bed7797/attachment.html>