bug#56521: Add 'take' list operation [PATCH]

["Mattias Engdegård" <mattiase@acm.org>]

[-- Attachment #1: Type: text/plain, Size: 2403 bytes --]

A basic list operation that is often useful is 'take', that extracts the N first elements of a list. The attached patch adds 'take' as a built-in function.

We already have its complement, `drop`, under the name `nthcdr`. (I wouldn't mind adding `drop` as an alias but it's not very important.)

How would it compare to existing alternatives, or to a pure Lisp implementation? Here are relative timings (smaller is better), sans GC.
N/M means taking N elements from a list of M.

|            | 5/10 | 9999/10000 | 1/10 |  1/0 |
|------------+------+------------+------+------|
| take       | 1.00 |       1.00 | 1.00 | 1.00 |
|------------+------+------------+------+------|
| seq-take   | 4.90 |       3.45 | 5.82 | 4.95 |
| -take      | 4.01 |       4.92 | 2.86 | 1.54 |
|------------+------+------------+------+------|
| fwd        | 2.89 |       3.76 | 1.77 | 1.25 |
| rev        | 2.90 |       3.45 | 2.06 | 1.38 |
| cl-loop    | 3.18 |       3.82 | 2.21 | 1.65 |
| butlast    | 3.58 |       1.73 | 6.59 | 2.33 |
|------------+------+------------+------+------|
| ntake (el) | 0.80 |       0.20 | 1.51 | 1.40 |
| ntake (C)  | 0.48 |       0.41 | 0.83 | 0.99 |

`seq-take` and `-take` are existing implementations from seq.el and dash.el respectively.  `fwd`, `rev`, `cl-loop` and `butlast` are 
alternative implementations in elisp. `ntake` are elisp and C implementations of a destructive take operation

A common replacement is using `butlast` but as we see that is very inefficient (worse than the table suggests since GC costs are not included). It also doesn't work for circular or dotted lists.

The C implementation would, of course, be used to implement `seq-take` for lists and speed up existing code. 

Adding `ntake` as a C primitive is not quite as beneficial since the elisp implementation does fairly well. (I'm not sure why Elisp is actually faster than C in the 9999/10000 case; maybe I made a mistake, or it has something to do with `nthcdr` having its own bytecode). I included `ntake` in the patch for reference and because it's Lisp tradition to have faster destructive 'n-' variants of list functions.

The patch is just a draft; there will be tests and manual text.
There are details that can be debated. For example, we don't error on negative N. It might be useful to allow the compiler to partially evaluate calls where N<2 or LIST=nil.


[-- Attachment #2: take.diff --]
[-- Type: application/octet-stream, Size: 2057 bytes --]

diff --git a/src/fns.c b/src/fns.c
index 1f57e675b1..2f507573a1 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1557,6 +1557,61 @@ substring_both (Lisp_Object string, ptrdiff_t from, ptrdiff_t from_byte,
   return res;
 }
 \f
+DEFUN ("take", Ftake, Stake, 2, 2, 0,
+       doc: /* Return the first N elements of LIST.
+If N is zero or negative, return nil.
+If LIST is not more than N elements long, return it (or a copy).  */)
+  (Lisp_Object n, Lisp_Object list)
+{
+  CHECK_FIXNUM (n);
+  EMACS_INT m = XFIXNUM (n);
+  if (m <= 0)
+    return Qnil;
+  CHECK_LIST (list);
+  if (NILP (list))
+    return Qnil;
+  Lisp_Object ret = Fcons (XCAR (list), Qnil);
+  Lisp_Object prev = ret;
+  m--;
+  list = XCDR (list);
+  while (m > 0 && CONSP (list))
+    {
+      Lisp_Object p = Fcons (XCAR (list), Qnil);
+      XSETCDR (prev, p);
+      prev = p;
+      m--;
+      list = XCDR (list);
+    }
+  if (m > 0 && !NILP (list))
+    wrong_type_argument (Qlistp, list);
+  return ret;
+}
+
+DEFUN ("ntake", Fntake, Sntake, 2, 2, 0,
+       doc: /* Return the first N elements of LIST, destructively.
+If N is zero or negative, return nil.
+If LIST is not more than N elements long, return it.  */)
+  (Lisp_Object n, Lisp_Object list)
+{
+  CHECK_FIXNUM (n);
+  EMACS_INT m = XFIXNUM (n);
+  if (m <= 0)
+    return Qnil;
+  CHECK_LIST (list);
+  Lisp_Object tail = list;
+  --m;
+  while (m > 0 && CONSP (tail))
+    {
+      tail = XCDR (tail);
+      m--;
+    }
+  if (CONSP (tail))
+    XSETCDR (tail, Qnil);
+  else if (!NILP (tail))
+    wrong_type_argument (Qlistp, list);
+  return list;
+}
+
 DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
        doc: /* Take cdr N times on LIST, return the result.  */)
   (Lisp_Object n, Lisp_Object list)
@@ -6082,6 +6137,8 @@ syms_of_fns (void)
   defsubr (&Scopy_alist);
   defsubr (&Ssubstring);
   defsubr (&Ssubstring_no_properties);
+  defsubr (&Stake);
+  defsubr (&Sntake);
   defsubr (&Snthcdr);
   defsubr (&Snth);
   defsubr (&Selt);