unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Add a function for building sort predicates
@ 2024-02-01 17:06 Michael Heerdegen
  2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
  2024-02-01 22:48 ` [External] : " Drew Adams
  0 siblings, 2 replies; 16+ messages in thread
From: Michael Heerdegen @ 2024-02-01 17:06 UTC (permalink / raw)
  To: Emacs Development

Hello,

I looked at how "package.el" defines the sort predicates for the used
tabulated list view - for example, `package-menu--status-predicate':

#+begin_src emacs-lisp
(defun package-menu--status-predicate (A B)
  "Predicate to sort \"*Packages*\" buffer by the status column.
This is used for `tabulated-list-format' in `package-menu-mode'."
  (let ((sA (aref (cadr A) 2))
        (sB (aref (cadr B) 2)))
    (cond ((string= sA sB)
           (package-menu--name-predicate A B))
          ((string= sA "new") t)
          ((string= sB "new") nil)
          ((string-prefix-p "avail" sA)
           (if (string-prefix-p "avail" sB)
               (package-menu--name-predicate A B)
             t))
          ((string-prefix-p "avail" sB) nil)
          ((string= sA "installed") t)
          ((string= sB "installed") nil)
          ((string= sA "dependency") t)
          ((string= sB "dependency") nil)
          ((string= sA "source") t)
          ((string= sB "source") nil)
          ((string= sA "unsigned") t)
          ...
          (t (string< sA sB)))))
#+end_src

This is hard to read and maintain, 0% user configurable, and it's not
easy to add additional "layers", like, "sort packages with equal states
first by archive name, and only then by name".

I want to suggest to add a function for defining sort predicates for
cases like these (especially having tabulated-list-mode in mind, but not
only - sorting is a common task).

Here is what I would imagine:

#+begin_src emacs-lisp
;; -*- lexical-binding: t -*-

(defun make-sort-pred (rules)
  "Return a sort predicate according to the sort RULES.
The returned predicate will accept two arguments A and B.  When
called, it will try RULES in order to decide whether A < B and
return non-nil in that case and nil when B <= A.  When no rule can
decide whether A < B, the predicate will also return nil.

RULES is a list of sort specifications using one of the formats
explained below.

The allowed formats of the specification lists in RULES are:

 -- (KEYFUN PRED)

This is like

       (lambda (a b)
         (funcall PRED (funcall KEYFUN a)
                       (funcall KEYFUN b)))

 -- (KEYFUN EQUAL-TEST . KEYLIST)

This spec allows to specify the order of keys explicitly when the
number of possible keys is small by specifying an accordingly
ordered KEYLIST directly.

A test using this rule form will first call KEYFUN with the
arguments A and B to get K-A and K-B.  Then, using the equality
test EQUAL-TEST, it is tested to which of the elements in KEYLIST
K-A and K-B are equal.  It is decided whether A < B using the
natural order of the KEYLIST elements.  Keys not found in KEYLIST
are treated it as if coming after all of its elements.  Elements
for that KEYFUN yields `equal' values are considered
indistinguishable.

 -- (KEYFUN EQUAL-TEST GET-KEYLIST)

This works exactly like the above spec - the only difference is
that GET-KEYLIST is either a symbol whose `symbol-value' will be
consulted, or a function accepting zero arguments to obtain the
KEYLIST to use, at run-time.  In the latter case the function
should be accordingly cheap when called and avoid unnecessary
consing.


Example 1: Sort a list like this:

  ((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3)
   (\"c\" 1) (\"a\" 2) (\"b\" 2))

first by the first element, then by the second:

(sort \\='((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3)
        (\"c\" 1) (\"a\" 2) (\"b\" 2))
      (make-sort-pred `((,#'car  ,#'string<)
                        (,#'cadr ,#'<))))

Example 2: Create a sort predicate suitable for sorting the list
of packages for M-x list-packages.  We want to have all \"new\"
packages listed first, then all obsolete packages, according to
the following list:

  (defvar my-package-menu--status-sorting-order
   \\='(\"new\" \"obsolete\" \"held\" \"external\" ...))

Package in the same category should be sorted by archive in a certain
order, and last by name:

(defalias \\='my-package-menu--status-predicate
  (make-sort-pred
   `((,(lambda (x) (aref (cadr x) 2))
      ,#'string= my-package-menu--status-sorting-order)
     (,(lambda (x) (package-desc-archive (car x)))
      ,#'equal \"gnu\" \"nongnu\" \"melpa\" nil)
     (,#'identity ,#'package-menu--name-predicate))))"

  (let ((result (make-symbol "result")))
    (cl-flet ((compare-with (test a b)
                (cond
                 ((funcall test a b) (throw result t))
                 ((funcall test b a) (throw result nil)))))
      (let ((rules
             ;; translate RULES to test functions
             (mapcar
              (pcase-lambda (`(,keyfun . ,rule))
                (if (cdr rule)
                    (let* ((test (car rule))
                           (testfun (lambda (x y)
                                      (funcall test y (funcall keyfun x))))
                           (keys (cdr rule))
                           (ckeys (car keys)))
                      (cl-flet ((keys (cond ((cdr keys) (lambda () keys))
                                            ((symbolp ckeys)
                                             (lambda () (symbol-value ckeys)))
                                            (t (lambda () (funcall ckeys))))))
                        (lambda (a b)
                          (cl-block nil
                            (let ((keys (keys)))
                              (while keys
                                (let ((key (pop keys)))
                                  (cond ((funcall testfun a key)
                                         (if (funcall testfun b key)
                                             (cl-return)
                                           (throw result t)))
                                        ((funcall testfun b key)
                                         (throw result nil))))))))))
                  (lambda (a b)
                    (compare-with
                     (car rule)
                     (funcall keyfun a) (funcall keyfun b)))))
                     rules)))

        (lambda (a b)
          (catch result
            ;; any rule throws 'result' when a<b is decidable with it
            (dolist (rule rules) (funcall rule a b))
            ;; no rule was able to decide - return nil for stable sorting
            nil))))))
#+end_src

Running time is comparable witho the existing code.

Would we want to add something like this?  And to which library?  I
would like to prepare a patch.


TIA,

Michael.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 17:06 Add a function for building sort predicates Michael Heerdegen
@ 2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
  2024-02-01 17:26   ` Eli Zaretskii
  2024-02-01 18:04   ` Michael Heerdegen via Emacs development discussions.
  2024-02-01 22:48 ` [External] : " Drew Adams
  1 sibling, 2 replies; 16+ messages in thread
From: Daniel Mendler via Emacs development discussions. @ 2024-02-01 17:19 UTC (permalink / raw)
  To: Michael Heerdegen; +Cc: Emacs Development

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hello,
>
> I looked at how "package.el" defines the sort predicates for the used
> tabulated list view - for example, `package-menu--status-predicate':
>
> #+begin_src emacs-lisp
> (defun package-menu--status-predicate (A B)
>   "Predicate to sort \"*Packages*\" buffer by the status column.
> This is used for `tabulated-list-format' in `package-menu-mode'."
>   (let ((sA (aref (cadr A) 2))
>         (sB (aref (cadr B) 2)))
>     (cond ((string= sA sB)
>            (package-menu--name-predicate A B))
>           ((string= sA "new") t)
>           ((string= sB "new") nil)
>           ((string-prefix-p "avail" sA)
>            (if (string-prefix-p "avail" sB)
>                (package-menu--name-predicate A B)
>              t))
>           ((string-prefix-p "avail" sB) nil)
>           ((string= sA "installed") t)
>           ((string= sB "installed") nil)
>           ((string= sA "dependency") t)
>           ((string= sB "dependency") nil)
>           ((string= sA "source") t)
>           ((string= sB "source") nil)
>           ((string= sA "unsigned") t)
>           ...
>           (t (string< sA sB)))))
> #+end_src
>
>
> This is hard to read and maintain, 0% user configurable, and it's not
> easy to add additional "layers", like, "sort packages with equal states
> first by archive name, and only then by name".
>
> I want to suggest to add a function for defining sort predicates for
> cases like these (especially having tabulated-list-mode in mind, but not
> only - sorting is a common task).
>
> Here is what I would imagine:
>
> #+begin_src emacs-lisp
> ;; -*- lexical-binding: t -*-
>
> (defun make-sort-pred (rules)
>   "Return a sort predicate according to the sort RULES.
> The returned predicate will accept two arguments A and B.  When
> called, it will try RULES in order to decide whether A < B and
> return non-nil in that case and nil when B <= A.  When no rule can
> decide whether A < B, the predicate will also return nil.
>
> RULES is a list of sort specifications using one of the formats
> explained below.
>
> The allowed formats of the specification lists in RULES are:
>
>  -- (KEYFUN PRED)
>
> This is like
>
>        (lambda (a b)
>          (funcall PRED (funcall KEYFUN a)
>                        (funcall KEYFUN b)))
>
>  -- (KEYFUN EQUAL-TEST . KEYLIST)
>
> This spec allows to specify the order of keys explicitly when the
> number of possible keys is small by specifying an accordingly
> ordered KEYLIST directly.
>
> A test using this rule form will first call KEYFUN with the
> arguments A and B to get K-A and K-B.  Then, using the equality
> test EQUAL-TEST, it is tested to which of the elements in KEYLIST
> K-A and K-B are equal.  It is decided whether A < B using the
> natural order of the KEYLIST elements.  Keys not found in KEYLIST
> are treated it as if coming after all of its elements.  Elements
> for that KEYFUN yields `equal' values are considered
> indistinguishable.
>
>  -- (KEYFUN EQUAL-TEST GET-KEYLIST)
>
> This works exactly like the above spec - the only difference is
> that GET-KEYLIST is either a symbol whose `symbol-value' will be
> consulted, or a function accepting zero arguments to obtain the
> KEYLIST to use, at run-time.  In the latter case the function
> should be accordingly cheap when called and avoid unnecessary
> consing.
>
>
> Example 1: Sort a list like this:
>
>   ((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3)
>    (\"c\" 1) (\"a\" 2) (\"b\" 2))
>
> first by the first element, then by the second:
>
> (sort \\='((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3)
>         (\"c\" 1) (\"a\" 2) (\"b\" 2))
>       (make-sort-pred `((,#'car  ,#'string<)
>                         (,#'cadr ,#'<))))
>
> Example 2: Create a sort predicate suitable for sorting the list
> of packages for M-x list-packages.  We want to have all \"new\"
> packages listed first, then all obsolete packages, according to
> the following list:
>
>   (defvar my-package-menu--status-sorting-order
>    \\='(\"new\" \"obsolete\" \"held\" \"external\" ...))
>
> Package in the same category should be sorted by archive in a certain
> order, and last by name:
>
> (defalias \\='my-package-menu--status-predicate
>   (make-sort-pred
>    `((,(lambda (x) (aref (cadr x) 2))
>       ,#'string= my-package-menu--status-sorting-order)
>      (,(lambda (x) (package-desc-archive (car x)))
>       ,#'equal \"gnu\" \"nongnu\" \"melpa\" nil)
>      (,#'identity ,#'package-menu--name-predicate))))"
>
>   (let ((result (make-symbol "result")))
>     (cl-flet ((compare-with (test a b)
>                 (cond
>                  ((funcall test a b) (throw result t))
>                  ((funcall test b a) (throw result nil)))))
>       (let ((rules
>              ;; translate RULES to test functions
>              (mapcar
>               (pcase-lambda (`(,keyfun . ,rule))
>                 (if (cdr rule)
>                     (let* ((test (car rule))
>                            (testfun (lambda (x y)
>                                       (funcall test y (funcall keyfun x))))
>                            (keys (cdr rule))
>                            (ckeys (car keys)))
>                       (cl-flet ((keys (cond ((cdr keys) (lambda () keys))
>                                             ((symbolp ckeys)
>                                              (lambda () (symbol-value ckeys)))
>                                             (t (lambda () (funcall ckeys))))))
>                         (lambda (a b)
>                           (cl-block nil
>                             (let ((keys (keys)))
>                               (while keys
>                                 (let ((key (pop keys)))
>                                   (cond ((funcall testfun a key)
>                                          (if (funcall testfun b key)
>                                              (cl-return)
>                                            (throw result t)))
>                                         ((funcall testfun b key)
>                                          (throw result nil))))))))))
>                   (lambda (a b)
>                     (compare-with
>                      (car rule)
>                      (funcall keyfun a) (funcall keyfun b)))))
>                      rules)))
>
>         (lambda (a b)
>           (catch result
>             ;; any rule throws 'result' when a<b is decidable with it
>             (dolist (rule rules) (funcall rule a b))
>             ;; no rule was able to decide - return nil for stable sorting
>             nil))))))
> #+end_src
>
> Running time is comparable witho the existing code.
>
> Would we want to add something like this?  And to which library?  I
> would like to prepare a patch.

That's a useful addition. Did you consider creating a macro, which will
lead to a more efficient predicate, or is `make-sort-pred' intended to
be used in scenarios with customizable predicate rules, such that the
rules have to be processed at runtime?

Daniel



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
@ 2024-02-01 17:26   ` Eli Zaretskii
  2024-02-01 18:10     ` Michael Heerdegen via Emacs development discussions.
  2024-02-01 18:04   ` Michael Heerdegen via Emacs development discussions.
  1 sibling, 1 reply; 16+ messages in thread
From: Eli Zaretskii @ 2024-02-01 17:26 UTC (permalink / raw)
  To: Daniel Mendler; +Cc: michael_heerdegen, emacs-devel

> Cc: Emacs Development <emacs-devel@gnu.org>
> Date: Thu, 01 Feb 2024 18:19:47 +0100
> From:  Daniel Mendler via "Emacs development discussions." <emacs-devel@gnu.org>
> 
> > Would we want to add something like this?  And to which library?  I
> > would like to prepare a patch.
> 
> That's a useful addition. Did you consider creating a macro, which will
> lead to a more efficient predicate, or is `make-sort-pred' intended to
> be used in scenarios with customizable predicate rules, such that the
> rules have to be processed at runtime?

How about adding a more user-friendly UI for customizing the sorting?
Surely, we could come up with something easier to use than having to
write a non-trivial sort comparison function?  This is all about
defining a "collation order" for a fixed and small set of status
values, right?



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
  2024-02-01 17:26   ` Eli Zaretskii
@ 2024-02-01 18:04   ` Michael Heerdegen via Emacs development discussions.
  2024-02-01 18:23     ` Daniel Mendler via Emacs development discussions.
  1 sibling, 1 reply; 16+ messages in thread
From: Michael Heerdegen via Emacs development discussions. @ 2024-02-01 18:04 UTC (permalink / raw)
  To: emacs-devel

Daniel Mendler via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> That's a useful addition. Did you consider creating a macro, which will
> lead to a more efficient predicate

I did consider that, but I doubt that would lead to significantly more
efficient code because...

>,or is `make-sort-pred' intended to be used in scenarios with
>customizable predicate rules, such that the rules have to be processed
>at runtime?

the return value is a closure (last few lines in the code) where the
processing of the rules already had happened at definition time.  Using
a macro the code would maybe be 10% faster or so... I thought it would
not be worth it.

Michael.




^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 17:26   ` Eli Zaretskii
@ 2024-02-01 18:10     ` Michael Heerdegen via Emacs development discussions.
  2024-02-01 19:09       ` Eli Zaretskii
  0 siblings, 1 reply; 16+ messages in thread
From: Michael Heerdegen via Emacs development discussions. @ 2024-02-01 18:10 UTC (permalink / raw)
  To: emacs-devel

Eli Zaretskii <eliz@gnu.org> writes:

> How about adding a more user-friendly UI for customizing the sorting?

I consider this only as a start.  With UI you mean customize?  Anyway,
the answer is probably YES.

> This is all about defining a "collation order" for a fixed and small
> set of status values, right?

Currently, yes.  But maybe we want to add more "rule" types in the
future, I don't yet know.  My starting point was to factor the code to
make it better understandable.

Michael.




^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 18:04   ` Michael Heerdegen via Emacs development discussions.
@ 2024-02-01 18:23     ` Daniel Mendler via Emacs development discussions.
  2024-02-01 19:22       ` Michael Heerdegen
  0 siblings, 1 reply; 16+ messages in thread
From: Daniel Mendler via Emacs development discussions. @ 2024-02-01 18:23 UTC (permalink / raw)
  To: Michael Heerdegen via Emacs development discussions.; +Cc: Michael Heerdegen

Michael Heerdegen via "Emacs development discussions."
<emacs-devel@gnu.org> writes:

> Daniel Mendler via "Emacs development discussions."
> <emacs-devel@gnu.org> writes:
>
>> That's a useful addition. Did you consider creating a macro, which will
>> lead to a more efficient predicate
>
> I did consider that, but I doubt that would lead to significantly more
> efficient code because...
>
>>,or is `make-sort-pred' intended to be used in scenarios with
>>customizable predicate rules, such that the rules have to be processed
>>at runtime?
>
> the return value is a closure (last few lines in the code) where the
> processing of the rules already had happened at definition time.  Using
> a macro the code would maybe be 10% faster or so... I thought it would
> not be worth it.

Did you perform some measurements, comparing with the hand-written
predicate in package.el? The code does not look efficient with the
function calls and the throws. In contrast, if the macro creates a
sequence of conditions the native compiler can optimize the result. It
all depends on the use case. If the rules are supposed to be
customizable and the lists are short, the dynamic approach will likely
work well enough. For long lists an efficient sort predicate makes a
difference in my experience, e.g., in a dynamically updating completion
UI with thousands of candidates, since the predicate is called very
often.

Daniel



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 18:10     ` Michael Heerdegen via Emacs development discussions.
@ 2024-02-01 19:09       ` Eli Zaretskii
  2024-02-02 20:11         ` Michael Heerdegen
  0 siblings, 1 reply; 16+ messages in thread
From: Eli Zaretskii @ 2024-02-01 19:09 UTC (permalink / raw)
  To: Michael Heerdegen; +Cc: emacs-devel

> Date: Thu, 01 Feb 2024 19:10:58 +0100
> From:  Michael Heerdegen via "Emacs development discussions." <emacs-devel@gnu.org>
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > How about adding a more user-friendly UI for customizing the sorting?
> 
> I consider this only as a start.  With UI you mean customize?  Anyway,
> the answer is probably YES.

Even a simple data structure should be easier than a full-fledged
function.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 18:23     ` Daniel Mendler via Emacs development discussions.
@ 2024-02-01 19:22       ` Michael Heerdegen
  2024-02-01 20:19         ` Daniel Mendler via Emacs development discussions.
  0 siblings, 1 reply; 16+ messages in thread
From: Michael Heerdegen @ 2024-02-01 19:22 UTC (permalink / raw)
  To: Daniel Mendler; +Cc: Michael Heerdegen via Emacs development discussions.

Daniel Mendler <mail@daniel-mendler.de> writes:

> Did you perform some measurements, comparing with the hand-written
> predicate in package.el?  The code does not look efficient with the
> function calls and the throws.

My version was around 6% slower. Using dynamic lookup of the key order.
I did not try with native compiling.

> In contrast, if the macro creates a sequence of conditions the native
> compiler can optimize the result. It all depends on the use case. If
> the rules are supposed to be customizable and the lists are short, the
> dynamic approach will likely work well enough. For long lists an
> efficient sort predicate makes a difference in my experience, e.g., in
> a dynamically updating completion UI with thousands of candidates,
> since the predicate is called very often.

A disadvantage is that custom option will have to introduce new :set
dependencies, I wanted to avoid that.

But in some cases the speed difference might be worth such an
optimization.  If you want to experiment, please be my guest.

Michael.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 19:22       ` Michael Heerdegen
@ 2024-02-01 20:19         ` Daniel Mendler via Emacs development discussions.
  0 siblings, 0 replies; 16+ messages in thread
From: Daniel Mendler via Emacs development discussions. @ 2024-02-01 20:19 UTC (permalink / raw)
  To: Michael Heerdegen; +Cc: Michael Heerdegen via Emacs development discussions.

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Daniel Mendler <mail@daniel-mendler.de> writes:
>
>> Did you perform some measurements, comparing with the hand-written
>> predicate in package.el?  The code does not look efficient with the
>> function calls and the throws.
>
> My version was around 6% slower. Using dynamic lookup of the key order.
> I did not try with native compiling.

Would be interesting to see the results with native compilation. I will
try it when I find time.

>> In contrast, if the macro creates a sequence of conditions the native
>> compiler can optimize the result. It all depends on the use case. If
>> the rules are supposed to be customizable and the lists are short, the
>> dynamic approach will likely work well enough. For long lists an
>> efficient sort predicate makes a difference in my experience, e.g., in
>> a dynamically updating completion UI with thousands of candidates,
>> since the predicate is called very often.
>
> A disadvantage is that custom option will have to introduce new :set
> dependencies, I wanted to avoid that.

What do you mean by :set dependencies? If we use a macro, customization
is not possible anymore. So if customization of the rules is a
requirement, then we have to go with a function. Another optimization
option is to transparently compile to byte code. Iirc such an approach
was discussed for `buffer-match-p'.

> But in some cases the speed difference might be worth such an
> optimization.  If you want to experiment, please be my guest.

Yes. The question is where this predicate builder is supposed to be
used. Probably interfaces like list-packages or generally tabulated-list
buffers would not profit so much from optimization. With ELPA and MELPA
the packages buffer has around 6000 entries.

Daniel



^ permalink raw reply	[flat|nested] 16+ messages in thread

* RE: [External] : Add a function for building sort predicates
  2024-02-01 17:06 Add a function for building sort predicates Michael Heerdegen
  2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
@ 2024-02-01 22:48 ` Drew Adams
  2024-02-02 20:05   ` Michael Heerdegen
  1 sibling, 1 reply; 16+ messages in thread
From: Drew Adams @ 2024-02-01 22:48 UTC (permalink / raw)
  To: Michael Heerdegen, Emacs Development

> This is hard to read and maintain, 0% user configurable, and it's not
> easy to add additional "layers", like, "sort packages with equal states
> first by archive name, and only then by name".
>
> I want to suggest to add a function for defining sort predicates for
> cases like these (especially having tabulated-list-mode in mind, but
> not only - sorting is a common task).

Yes.  Compose predicates to create new predicates:

First this test.  If it can't decide, then the next
test.  If it can't decide, then the next test...
(Similar to `run-hooks-with-args-until-* behavior.)

Let a given predicate decide true, false, or dunno.
Only if its result is `dunno' is the next predicate
tried.

There can be a little more to it.  See this for
something quite similar:

https://www.emacswiki.org/emacs/ApplesAndOranges

(Since 2009.)



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: [External] : Add a function for building sort predicates
  2024-02-01 22:48 ` [External] : " Drew Adams
@ 2024-02-02 20:05   ` Michael Heerdegen
  2024-02-02 22:30     ` Drew Adams
  0 siblings, 1 reply; 16+ messages in thread
From: Michael Heerdegen @ 2024-02-02 20:05 UTC (permalink / raw)
  To: Drew Adams; +Cc: Emacs Development

Drew Adams <drew.adams@oracle.com> writes:

> There can be a little more to it.  See this for
> something quite similar:
>
> https://www.emacswiki.org/emacs/ApplesAndOranges

Thanks.

I think my approach covers all of the cases mentioned there, at least
when you specify sort predicate definitions in the rule list
recursively.

Michael.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-01 19:09       ` Eli Zaretskii
@ 2024-02-02 20:11         ` Michael Heerdegen
  2024-02-03  2:55           ` Emanuel Berg
  2024-02-03  7:08           ` Eli Zaretskii
  0 siblings, 2 replies; 16+ messages in thread
From: Michael Heerdegen @ 2024-02-02 20:11 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: emacs-devel

Eli Zaretskii <eliz@gnu.org> writes:

> > I consider this only as a start.  With UI you mean customize?  Anyway,
> > the answer is probably YES.
>
> Even a simple data structure should be easier than a full-fledged
> function.

Not sure I understand what you are getting at.

In my code example, the data structure is the specification of the rules
in the call - a nested list, suitable for this task.  We need something
that makes the structure being "applicable" by `sort' - this is the
function implementation.  I'm probably misunderstanding.

Michael.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* RE: [External] : Add a function for building sort predicates
  2024-02-02 20:05   ` Michael Heerdegen
@ 2024-02-02 22:30     ` Drew Adams
  0 siblings, 0 replies; 16+ messages in thread
From: Drew Adams @ 2024-02-02 22:30 UTC (permalink / raw)
  To: Michael Heerdegen; +Cc: Emacs Development

> > See this for something quite similar:
> > https://www.emacswiki.org/emacs/ApplesAndOranges
> 
> Thanks.
> 
> I think my approach covers all of the cases
> mentioned there, at least when you specify
> sort predicate definitions in the rule list
> recursively.

Didn't mean to suggest otherwise.  I like it.

The "top-level" bit of your code:

(catch result
  ;; any rule throws 'result' when a<b is
  ;; decidable with it
  (dolist (rule rules) (funcall rule a b))
  ;; no rule was able to decide - return nil
  ;; for stable sorting
  nil))

is similar to mine:

(defun bmkp-multi-sort (b1 b2)
  (let ((preds       (car bmkp-sort-comparer))
        (final-pred  (cadr bmkp-sort-comparer))
        (result      nil))
    (when bmkp-reverse-multi-sort-p
      (setq preds  (reverse preds)))
    (catch 'bmkp-multi-sort
      (dolist (pred  preds)
        (setq result  (funcall pred b1 b2))
        (when (consp result)
          (when bmkp-reverse-multi-sort-p
            (setq result  (list (not (car result)))))
          (throw 'bmkp-multi-sort (car result))))
      (and final-pred
           (if bmkp-reverse-multi-sort-p
               (not (funcall final-pred b1 b2))
             (funcall final-pred b1 b2))))))

In fact, that's all the code I have for this.

User code just binds `bmkp-sort-comparer' to
a list of predicates (like your rules list).

That multi-sort function is called in one
place in my code for use with completion, and
in one place for use in a displayed bookmark
list (different libraries for those use cases).

It would similarly be used in a single place
in user code for a given sorting purpose.

Because I use a variable (well, two - one for
each of those use cases), code that wants a
different sort order for a given context can
just bind the variable to a different "rules"
list.

The code that sorts for completion, and the
code that sorts the bookmark list, each
invoke the function (above) that iterates
over the predicates.

But code that wants different sort orders
within either of those use cases typically
just extends or modifies the default "rules"
list for the use case (completion or buffer
sorting).

E.g., there are many kinds of completion,
which can call for different sort orders.
Each completion context (e.g. command) can
override the default sorting behavior just
by binding the comparer variable to its own
list of predicates (rules).
___

(Maybe consider providing an easy way to get
the reverse sort order, as a nice-to-have?)




^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-02 20:11         ` Michael Heerdegen
@ 2024-02-03  2:55           ` Emanuel Berg
  2024-02-03  7:08           ` Eli Zaretskii
  1 sibling, 0 replies; 16+ messages in thread
From: Emanuel Berg @ 2024-02-03  2:55 UTC (permalink / raw)
  To: emacs-devel

Michael Heerdegen wrote:

>>> I consider this only as a start. With UI you mean
>>> customize? Anyway, the answer is probably YES.
>>
>> Even a simple data structure should be easier than
>> a full-fledged function.
>
> Not sure I understand what you are getting at.
>
> In my code example, the data structure is the specification
> of the rules in the call - a nested list, suitable for this
> task. We need something that makes the structure being
> "applicable" by `sort' - this is the function
> implementation. I'm probably misunderstanding.

Make a single function, "sort-this". If you send a data
structure that cannot be sorted just return it the way it is.
If someone comes up with a way to sort it it can be added.

So instead of the Unix "do one thing and do it well" it is "do
one thing that does everything".

(compute me)

-- 
underground experts united
https://dataswamp.org/~incal




^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-02 20:11         ` Michael Heerdegen
  2024-02-03  2:55           ` Emanuel Berg
@ 2024-02-03  7:08           ` Eli Zaretskii
  2024-02-03 10:35             ` Michael Heerdegen
  1 sibling, 1 reply; 16+ messages in thread
From: Eli Zaretskii @ 2024-02-03  7:08 UTC (permalink / raw)
  To: Michael Heerdegen; +Cc: emacs-devel

> From: Michael Heerdegen <michael_heerdegen@web.de>
> Cc: emacs-devel@gnu.org
> Date: Fri, 02 Feb 2024 21:11:26 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > > I consider this only as a start.  With UI you mean customize?  Anyway,
> > > the answer is probably YES.
> >
> > Even a simple data structure should be easier than a full-fledged
> > function.
> 
> Not sure I understand what you are getting at.

I mean something like a list data structure which determines the order
of sorting keys.  Users can define such data structures even if their
Lisp programming capabilities are relatively low or even nonexistent.

> In my code example, the data structure is the specification of the rules
> in the call - a nested list, suitable for this task.  We need something
> that makes the structure being "applicable" by `sort' - this is the
> function implementation.  I'm probably misunderstanding.

Or maybe I'm misunderstanding.  AFAIU, you and Daniel had in mind
adding a function which is the sort predicate, as the means for
customization of sorting.  My point is that users should preferably
not be required to customize such features by writing Lisp code.

Apologies if I misunderstood your suggestion, but in that case perhaps
you should explain it in more detail, including what will users have
to do to customize the sorting order.



^ permalink raw reply	[flat|nested] 16+ messages in thread

* Re: Add a function for building sort predicates
  2024-02-03  7:08           ` Eli Zaretskii
@ 2024-02-03 10:35             ` Michael Heerdegen
  0 siblings, 0 replies; 16+ messages in thread
From: Michael Heerdegen @ 2024-02-03 10:35 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: emacs-devel

Eli Zaretskii <eliz@gnu.org> writes:

> My point is that users should preferably not be required to customize
> such features by writing Lisp code.

Thx, now it's clear, and I agree.

Michael.



^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2024-02-03 10:35 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-02-01 17:06 Add a function for building sort predicates Michael Heerdegen
2024-02-01 17:19 ` Daniel Mendler via Emacs development discussions.
2024-02-01 17:26   ` Eli Zaretskii
2024-02-01 18:10     ` Michael Heerdegen via Emacs development discussions.
2024-02-01 19:09       ` Eli Zaretskii
2024-02-02 20:11         ` Michael Heerdegen
2024-02-03  2:55           ` Emanuel Berg
2024-02-03  7:08           ` Eli Zaretskii
2024-02-03 10:35             ` Michael Heerdegen
2024-02-01 18:04   ` Michael Heerdegen via Emacs development discussions.
2024-02-01 18:23     ` Daniel Mendler via Emacs development discussions.
2024-02-01 19:22       ` Michael Heerdegen
2024-02-01 20:19         ` Daniel Mendler via Emacs development discussions.
2024-02-01 22:48 ` [External] : " Drew Adams
2024-02-02 20:05   ` Michael Heerdegen
2024-02-02 22:30     ` Drew Adams

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).