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

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)

Answer 2

From My Lisp Experiences and the Development of GNU Emacs:

There were people in those days, in 1985, who had one-megabyte machines without virtual memory. They wanted to be able to use GNU Emacs. This meant I had to keep the program as small as possible.

For instance, at the time the only looping construct was ‘while’, which was extremely simple. There was no way to break out of the ‘while’ statement, you just had to do a catch and a throw, or test a variable that ran the loop. That shows how far I was pushing to keep things small. We didn't have ‘caar’ and ‘cadr’ and so on; “squeeze out everything possible” was the spirit of GNU Emacs, the spirit of Emacs Lisp, from the beginning.

Obviously, machines are bigger now, and we don't do it that way anymore. We put in ‘caar’ and ‘cadr’ and so on, and we might put in another looping construct one of these days.

So my guess is, if you don't see it, it's not there.

Answer 3

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.