FR: -sort-keyed

[doublep]

I have already written the function, but then noticed in the docs that it can easily be composed from existing stuff:

(-sort-keyed key-computer comparator list) <==> (-sort (-on comparator key-computer) list)

Therefore I didn't finish my work and decided to ask if it is wanted first.

I still think that the function is useful:

• it calls key-comparator exactly N times, while existing function calls it O (N log N) times, which makes a significant difference if N is large and key-computer is non-trivial;
• its invocation is arguably easier to understand.

If this function is wanted, I can finish what I started with documentation and tests.

[Fuco1]

So basically you map, sort with remembering the order and then unmap?

[doublep]

I build list of conses of keys and values, sort that, and than map to discard keys. Here it is:

(defun -sort-keyed (key-computer comparator list)
  "Sort LIST by given keys, comparing them using COMPARATOR.
First KEY-COMPUTER is used to compute key value for each list
item.  Then resulting keys are sorted (stably) according to
COMPARATOR.  Finally, a copy of the original LIST is built and
rearranged in the same way.

LIST is not modified by side effects.  KEY-COMPARATOR is called
once for each element of LIST, i.e. with one argument.
COMPARATOR is called with two keys, and should return non-nil if
the first one (and thus its associated LIST element) should sort
before the second."
  (if (cdr list)
      (let (keyed-list)
        (--each list
          (!cons (cons (funcall key-computer it) it) keyed-list))
        ;; Reversing before sorting seems unnecessary, but it ensures
        ;; stability by restoring original order.  We don't use
        ;; '-call' because there's no need to copy argument.
        (--map (cdr it)
               (sort (nreverse keyed-list)
                     (lambda (a b) (funcall comparator (car a) (car b))))))
    (when list
      (list (car list)))))

[Fuco1]

Yea, this already exists in dash. The problem is that it doesn't work well without lexical scope (the lambda there can break quite easily). See -grade-up or -grade-down

[doublep]

No, the function I proposed is the same as (-sort (-on comparator key-computer) list), only more efficient in some cases. It doesn't return list of indices, but sorted copy of original list.

What is the problem with lambdas and non-lexical binding? That you can accidentally shadow a variable user depends on?

[Fuco1]

Consider for example

(let ((comparator (lambda (a b) (let (comparator) (funcall comparator a b)))))
  (sort '(1 2 3 4) comparator))

[Fuco1]

Well, that's a bit silly example... I'll try to come up with something better :D I'm not sure now it showcases what I wanted.

[Fuco1]

Can you open a PR with your implementation so we can review it?

[Fuco1]

Followed in the PR.