extract/slice/reorder lists in (emacs) lisp?

Question

In python, you might do something like

i = (0, 3, 2)
x = [x+1 for x in range(0,5)]
operator.itemgetter(*i)(x)

to get (1, 4, 3). In (emacs) lisp, I wrote this function called extract which does something similar,

(defun extract (elems seq)
  (mapcar (lambda (x) (nth x seq)) elems))

(extract '(0 3 2) (number-sequence 1 5))

but I feel like there should be something built in? All I know is first, last, rest, nth, car, cdr... What's the way to go? ~ Thanks in advance ~

Answer 1

If your problem is the speed then use (vector 1 2 3 4 5) instead of a list, and (aref vec index) to get the element.

(defun extract (elems seq)
  (let ((av (vconcat seq)))
    (mapcar (lambda (x) (aref av x)) elems)))

If you're going to extract from the same sequence many times of course it make sense to store the sequence in a vector just once. Python lists are indeed one-dimensional arrays, the equivalent in LISP are vectors.

Answer 2

I've only done simple scripting in elisp, but it's a relatively small language. And extract is a very inefficient function on linked lists, which is the default data structure in emacs lisp. So it's unlikely to be built-in.

Your solution is the best straightforward one. It's n^2, but to make it faster requires a lot more code.

Below is a guess at how it might work, but it might also be totally off base:

1. sort elems (n log n)
2. create a map that maps elements in sorted elem to their indices in original elem (probably n log n, maybe n)
3. iterate through seq and sorted elem. Keep only the indices in sorted elem (probably n, maybe n log n, depending on whether it's a hash map or a tree map)
4. sort the result by the values of the elem mapping (n log n)