1 ;;; seq.el --- Sequence manipulation functions -*- lexical-binding: t -*-
3 ;; Copyright (C) 2014-2017 Free Software Foundation, Inc.
5 ;; Author: Nicolas Petton <nicolas@petton.fr>
10 ;; Maintainer: emacs-devel@gnu.org
12 ;; This file is part of GNU Emacs.
14 ;; GNU Emacs is free software: you can redistribute it and/or modify
15 ;; it under the terms of the GNU General Public License as published by
16 ;; the Free Software Foundation, either version 3 of the License, or
17 ;; (at your option) any later version.
19 ;; GNU Emacs is distributed in the hope that it will be useful,
20 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
21 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 ;; GNU General Public License for more details.
24 ;; You should have received a copy of the GNU General Public License
25 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
29 ;; Sequence-manipulation functions that complement basic functions
30 ;; provided by subr.el.
32 ;; All functions are prefixed with "seq-".
34 ;; All provided functions work on lists, strings and vectors.
36 ;; Functions taking a predicate or iterating over a sequence using a
37 ;; function as argument take the function as their first argument and
38 ;; the sequence as their second argument. All other functions take
39 ;; the sequence as their first argument.
41 ;; While seq.el version 1.8 is in GNU ELPA for convenience, seq.el
42 ;; version 2.0 requires Emacs>=25.1.
44 ;; seq.el can be extended to support new type of sequences. Here are
45 ;; the generic functions that must be implemented by new seq types:
51 ;; - `seq-into-sequence'
55 ;; All functions are tested in test/automated/seq-tests.el
59 (eval-when-compile (require 'cl-generic
))
60 (require 'cl-lib
) ;; for cl-subseq
62 (defmacro seq-doseq
(spec &rest body
)
63 "Loop over a sequence.
64 Evaluate BODY with VAR bound to each element of SEQUENCE, in turn.
66 Similar to `dolist' but can be applied to lists, strings, and vectors.
68 \(fn (VAR SEQUENCE) BODY...)"
69 (declare (indent 1) (debug ((symbolp form
&optional form
) body
)))
70 `(seq-do (lambda (,(car spec
))
74 (pcase-defmacro seq
(&rest patterns
)
75 "Build a `pcase' pattern that matches elements of SEQUENCE.
77 The `pcase' pattern will match each element of PATTERNS against the
78 corresponding element of SEQUENCE.
80 Extra elements of the sequence are ignored if fewer PATTERNS are
81 given, and the match does not fail."
83 ,@(seq--make-pcase-bindings patterns
)))
85 (defmacro seq-let
(args sequence
&rest body
)
86 "Bind the variables in ARGS to the elements of SEQUENCE, then evaluate BODY.
88 ARGS can also include the `&rest' marker followed by a variable
89 name to be bound to the rest of SEQUENCE."
90 (declare (indent 2) (debug (sexp form body
)))
91 `(pcase-let ((,(seq--make-pcase-patterns args
) ,sequence
))
95 ;;; Basic seq functions that have to be implemented by new sequence types
96 (cl-defgeneric seq-elt
(sequence n
)
97 "Return Nth element of SEQUENCE."
100 ;; Default gv setters for `seq-elt'.
101 ;; It can be a good idea for new sequence implementations to provide a
102 ;; "gv-setter" for `seq-elt'.
103 (cl-defmethod (setf seq-elt
) (store (sequence array
) n
)
104 (aset sequence n store
))
106 (cl-defmethod (setf seq-elt
) (store (sequence cons
) n
)
107 (setcar (nthcdr n sequence
) store
))
109 (cl-defgeneric seq-length
(sequence)
110 "Return the number of elements of SEQUENCE."
113 (cl-defgeneric seq-do
(function sequence
)
114 "Apply FUNCTION to each element of SEQUENCE, presumably for side effects.
116 (mapc function sequence
))
118 (defalias 'seq-each
#'seq-do
)
120 (defun seq-do-indexed (function sequence
)
121 "Apply FUNCTION to each element of SEQUENCE and return nil.
122 Unlike `seq-map', FUNCTION takes two arguments: the element of
123 the sequence, and its index within the sequence."
125 (seq-do (lambda (elt)
126 (funcall function elt index
)
127 (setq index
(1+ index
)))
130 (cl-defgeneric seqp
(sequence)
131 "Return non-nil if SEQUENCE is a sequence, nil otherwise."
132 (sequencep sequence
))
134 (cl-defgeneric seq-copy
(sequence)
135 "Return a shallow copy of SEQUENCE."
136 (copy-sequence sequence
))
138 (cl-defgeneric seq-subseq
(sequence start
&optional end
)
139 "Return the sequence of elements of SEQUENCE from START to END.
142 If END is omitted, it defaults to the length of the sequence. If
143 START or END is negative, it counts from the end. Signal an
144 error if START or END are outside of the sequence (i.e too large
145 if positive or too small if negative)."
146 (cl-subseq sequence start end
))
149 (cl-defgeneric seq-map
(function sequence
)
150 "Return the result of applying FUNCTION to each element of SEQUENCE."
152 (seq-do (lambda (elt)
153 (push (funcall function elt
) result
))
157 (defun seq-map-indexed (function sequence
)
158 "Return the result of applying FUNCTION to each element of SEQUENCE.
159 Unlike `seq-map', FUNCTION takes two arguments: the element of
160 the sequence, and its index within the sequence."
162 (seq-map (lambda (elt)
164 (funcall function elt index
)
165 (setq index
(1+ index
))))
169 ;; faster implementation for sequences (sequencep)
170 (cl-defmethod seq-map (function (sequence sequence
))
171 (mapcar function sequence
))
173 (cl-defgeneric seq-mapn
(function sequence
&rest sequences
)
174 "Like `seq-map' but FUNCTION is mapped over all SEQUENCES.
175 The arity of FUNCTION must match the number of SEQUENCES, and the
176 mapping stops on the shortest sequence.
177 Return a list of the results.
179 \(fn FUNCTION SEQUENCES...)"
181 (sequences (seq-map (lambda (s)
183 (cons sequence sequences
))))
184 (while (not (memq nil sequences
))
185 (push (apply function
(seq-map #'car sequences
)) result
)
186 (setq sequences
(seq-map #'cdr sequences
)))
189 (cl-defgeneric seq-drop
(sequence n
)
190 "Remove the first N elements of SEQUENCE and return the result.
191 The result is a sequence of the same type as SEQUENCE.
193 If N is a negative integer or zero, SEQUENCE is returned."
196 (let ((length (seq-length sequence
)))
197 (seq-subseq sequence
(min n length
) length
))))
199 (cl-defgeneric seq-take
(sequence n
)
200 "Take the first N elements of SEQUENCE and return the result.
201 The result is a sequence of the same type as SEQUENCE.
203 If N is a negative integer or zero, an empty sequence is
205 (seq-subseq sequence
0 (min (max n
0) (seq-length sequence
))))
207 (cl-defgeneric seq-drop-while
(pred sequence
)
208 "Remove the successive elements of SEQUENCE for which PRED returns non-nil.
209 PRED is a function of one argument. The result is a sequence of
210 the same type as SEQUENCE."
211 (seq-drop sequence
(seq--count-successive pred sequence
)))
213 (cl-defgeneric seq-take-while
(pred sequence
)
214 "Take the successive elements of SEQUENCE for which PRED returns non-nil.
215 PRED is a function of one argument. The result is a sequence of
216 the same type as SEQUENCE."
217 (seq-take sequence
(seq--count-successive pred sequence
)))
219 (cl-defgeneric seq-empty-p
(sequence)
220 "Return non-nil if the SEQUENCE is empty, nil otherwise."
221 (= 0 (seq-length sequence
)))
223 (cl-defgeneric seq-sort
(pred sequence
)
224 "Sort SEQUENCE using PRED as comparison function.
225 The result is a sequence of the same type as SEQUENCE."
226 (let ((result (seq-sort pred
(append sequence nil
))))
227 (seq-into result
(type-of sequence
))))
229 (cl-defmethod seq-sort (pred (list list
))
230 (sort (seq-copy list
) pred
))
232 (defun seq-sort-by (function pred sequence
)
233 "Sort SEQUENCE using PRED as a comparison function.
234 Elements of SEQUENCE are transformed by FUNCTION before being
235 sorted. FUNCTION must be a function of one argument."
236 (seq-sort (lambda (a b
)
239 (funcall function b
)))
242 (cl-defgeneric seq-reverse
(sequence)
243 "Return a sequence with elements of SEQUENCE in reverse order."
245 (seq-map (lambda (elt)
248 (seq-into result
(type-of sequence
))))
250 ;; faster implementation for sequences (sequencep)
251 (cl-defmethod seq-reverse ((sequence sequence
))
254 (cl-defgeneric seq-concatenate
(type &rest sequences
)
255 "Concatenate SEQUENCES into a single sequence of type TYPE.
256 TYPE must be one of following symbols: vector, string or list.
258 \n(fn TYPE SEQUENCE...)"
259 (apply #'cl-concatenate type
(seq-map #'seq-into-sequence sequences
)))
261 (cl-defgeneric seq-into-sequence
(sequence)
262 "Convert SEQUENCE into a sequence.
264 The default implementation is to signal an error if SEQUENCE is not a
265 sequence, specific functions should be implemented for new types
267 (unless (sequencep sequence
)
268 (error "Cannot convert %S into a sequence" sequence
))
271 (cl-defgeneric seq-into
(sequence type
)
272 "Concatenate the elements of SEQUENCE into a sequence of type TYPE.
273 TYPE can be one of the following symbols: vector, string or
276 (`vector
(seq--into-vector sequence
))
277 (`string
(seq--into-string sequence
))
278 (`list
(seq--into-list sequence
))
279 (_ (error "Not a sequence type name: %S" type
))))
281 (cl-defgeneric seq-filter
(pred sequence
)
282 "Return a list of all the elements for which (PRED element) is non-nil in SEQUENCE."
283 (let ((exclude (make-symbol "exclude")))
284 (delq exclude
(seq-map (lambda (elt)
285 (if (funcall pred elt
)
290 (cl-defgeneric seq-remove
(pred sequence
)
291 "Return a list of all the elements for which (PRED element) is nil in SEQUENCE."
292 (seq-filter (lambda (elt) (not (funcall pred elt
)))
295 (cl-defgeneric seq-reduce
(function sequence initial-value
)
296 "Reduce the function FUNCTION across SEQUENCE, starting with INITIAL-VALUE.
298 Return the result of calling FUNCTION with INITIAL-VALUE and the
299 first element of SEQUENCE, then calling FUNCTION with that result and
300 the second element of SEQUENCE, then with that result and the third
301 element of SEQUENCE, etc.
303 If SEQUENCE is empty, return INITIAL-VALUE and FUNCTION is not called."
304 (if (seq-empty-p sequence
)
306 (let ((acc initial-value
))
307 (seq-doseq (elt sequence
)
308 (setq acc
(funcall function acc elt
)))
311 (cl-defgeneric seq-every-p
(pred sequence
)
312 "Return non-nil if (PRED element) is non-nil for all elements of SEQUENCE."
314 (seq-doseq (elt sequence
)
315 (or (funcall pred elt
)
316 (throw 'seq--break nil
)))
319 (cl-defgeneric seq-some
(pred sequence
)
320 "Return non-nil if PRED is satisfied for at least one element of SEQUENCE.
321 If so, return the first non-nil value returned by PRED."
323 (seq-doseq (elt sequence
)
324 (let ((result (funcall pred elt
)))
326 (throw 'seq--break result
))))
329 (cl-defgeneric seq-find
(pred sequence
&optional default
)
330 "Return the first element for which (PRED element) is non-nil in SEQUENCE.
331 If no element is found, return DEFAULT.
333 Note that `seq-find' has an ambiguity if the found element is
334 identical to DEFAULT, as it cannot be known if an element was
337 (seq-doseq (elt sequence
)
338 (when (funcall pred elt
)
339 (throw 'seq--break elt
)))
342 (cl-defgeneric seq-count
(pred sequence
)
343 "Return the number of elements for which (PRED element) is non-nil in SEQUENCE."
345 (seq-doseq (elt sequence
)
346 (when (funcall pred elt
)
347 (setq count
(+ 1 count
))))
350 (cl-defgeneric seq-contains
(sequence elt
&optional testfn
)
351 "Return the first element in SEQUENCE that is equal to ELT.
352 Equality is defined by TESTFN if non-nil or by `equal' if nil."
353 (seq-some (lambda (e)
354 (when (funcall (or testfn
#'equal
) elt e
)
358 (cl-defgeneric seq-position
(sequence elt
&optional testfn
)
359 "Return the index of the first element in SEQUENCE that is equal to ELT.
360 Equality is defined by TESTFN if non-nil or by `equal' if nil."
363 (seq-doseq (e sequence
)
364 (when (funcall (or testfn
#'equal
) e elt
)
365 (throw 'seq--break index
))
366 (setq index
(1+ index
)))
369 (cl-defgeneric seq-uniq
(sequence &optional testfn
)
370 "Return a list of the elements of SEQUENCE with duplicates removed.
371 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
373 (seq-doseq (elt sequence
)
374 (unless (seq-contains result elt testfn
)
375 (setq result
(cons elt result
))))
378 (cl-defgeneric seq-mapcat
(function sequence
&optional type
)
379 "Concatenate the result of applying FUNCTION to each element of SEQUENCE.
380 The result is a sequence of type TYPE, or a list if TYPE is nil."
381 (apply #'seq-concatenate
(or type
'list
)
382 (seq-map function sequence
)))
384 (cl-defgeneric seq-partition
(sequence n
)
385 "Return a list of the elements of SEQUENCE grouped into sub-sequences of length N.
386 The last sequence may contain less than N elements. If N is a
387 negative integer or 0, nil is returned."
390 (while (not (seq-empty-p sequence
))
391 (push (seq-take sequence n
) result
)
392 (setq sequence
(seq-drop sequence n
)))
395 (cl-defgeneric seq-intersection
(sequence1 sequence2
&optional testfn
)
396 "Return a list of the elements that appear in both SEQUENCE1 and SEQUENCE2.
397 Equality is defined by TESTFN if non-nil or by `equal' if nil."
398 (seq-reduce (lambda (acc elt
)
399 (if (seq-contains sequence2 elt testfn
)
402 (seq-reverse sequence1
)
405 (cl-defgeneric seq-difference
(sequence1 sequence2
&optional testfn
)
406 "Return a list of the elements that appear in SEQUENCE1 but not in SEQUENCE2.
407 Equality is defined by TESTFN if non-nil or by `equal' if nil."
408 (seq-reduce (lambda (acc elt
)
409 (if (not (seq-contains sequence2 elt testfn
))
412 (seq-reverse sequence1
)
415 (cl-defgeneric seq-group-by
(function sequence
)
416 "Apply FUNCTION to each element of SEQUENCE.
417 Separate the elements of SEQUENCE into an alist using the results as
418 keys. Keys are compared using `equal'."
421 (let* ((key (funcall function elt
))
422 (cell (assoc key acc
)))
424 (setcdr cell
(push elt
(cdr cell
)))
425 (push (list key elt
) acc
))
427 (seq-reverse sequence
)
430 (cl-defgeneric seq-min
(sequence)
431 "Return the smallest element of SEQUENCE.
432 SEQUENCE must be a sequence of numbers or markers."
433 (apply #'min
(seq-into sequence
'list
)))
435 (cl-defgeneric seq-max
(sequence)
436 "Return the largest element of SEQUENCE.
437 SEQUENCE must be a sequence of numbers or markers."
438 (apply #'max
(seq-into sequence
'list
)))
440 (defun seq--count-successive (pred sequence
)
441 "Return the number of successive elements for which (PRED element) is non-nil in SEQUENCE."
443 (len (seq-length sequence
)))
444 (while (and (< n len
)
445 (funcall pred
(seq-elt sequence n
)))
449 (defun seq--make-pcase-bindings (args)
450 "Return a list of bindings of the variables in ARGS to the elements of a sequence."
454 (seq-doseq (name args
)
458 (progn (push `(app (pcase--flip seq-drop
,index
)
459 ,(seq--elt-safe args
(1+ index
)))
461 (setq rest-marker t
)))
463 (push `(app (pcase--flip seq--elt-safe
,index
) ,name
) bindings
))))
464 (setq index
(1+ index
)))
467 (defun seq--make-pcase-patterns (args)
468 "Return a list of `(seq ...)' pcase patterns from the argument list ARGS."
470 (seq-map (lambda (elt)
472 (seq--make-pcase-patterns elt
)
476 ;; TODO: make public?
477 (defun seq--elt-safe (sequence n
)
478 "Return element of SEQUENCE at the index N.
479 If no element is found, return nil."
480 (ignore-errors (seq-elt sequence n
)))
482 (cl-defgeneric seq-random-elt
(sequence)
483 "Return a random element from SEQUENCE.
484 Signal an error if SEQUENCE is empty."
485 (if (seq-empty-p sequence
)
486 (error "Sequence cannot be empty")
487 (seq-elt sequence
(random (seq-length sequence
)))))
490 ;;; Optimized implementations for lists
492 (cl-defmethod seq-drop ((list list
) n
)
493 "Optimized implementation of `seq-drop' for lists."
496 (cl-defmethod seq-take ((list list
) n
)
497 "Optimized implementation of `seq-take' for lists."
499 (while (and list
(> n
0))
501 (push (pop list
) result
))
504 (cl-defmethod seq-drop-while (pred (list list
))
505 "Optimized implementation of `seq-drop-while' for lists."
506 (while (and list
(funcall pred
(car list
)))
507 (setq list
(cdr list
)))
510 (cl-defmethod seq-empty-p ((list list
))
511 "Optimized implementation of `seq-empty-p' for lists."
515 (defun seq--into-list (sequence)
516 "Concatenate the elements of SEQUENCE into a list."
519 (append sequence nil
)))
521 (defun seq--into-vector (sequence)
522 "Concatenate the elements of SEQUENCE into a vector."
523 (if (vectorp sequence
)
527 (defun seq--into-string (sequence)
528 "Concatenate the elements of SEQUENCE into a string."
529 (if (stringp sequence
)
533 (defun seq--activate-font-lock-keywords ()
534 "Activate font-lock keywords for some symbols defined in seq."
535 (font-lock-add-keywords 'emacs-lisp-mode
536 '("\\<seq-doseq\\>" "\\<seq-let\\>")))
538 (unless (fboundp 'elisp--font-lock-flush-elisp-buffers
)
539 ;; In Emacsā„25, (via elisp--font-lock-flush-elisp-buffers and a few others)
540 ;; we automatically highlight macros.
541 (add-hook 'emacs-lisp-mode-hook
#'seq--activate-font-lock-keywords
))