1 ;;; seq.el --- Sequence manipulation functions -*- lexical-binding: t -*-
3 ;; Copyright (C) 2014-2015 Free Software Foundation, Inc.
5 ;; Author: Nicolas Petton <petton.nicolas@gmail.com>
9 ;; Maintainer: emacs-devel@gnu.org
11 ;; This file is part of GNU Emacs.
13 ;; GNU Emacs is free software: you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation, either version 3 of the License, or
16 ;; (at your option) any later version.
18 ;; GNU Emacs is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; You should have received a copy of the GNU General Public License
24 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
28 ;; Sequence-manipulation functions that complement basic functions
29 ;; provided by subr.el.
31 ;; All functions are prefixed with "seq-".
33 ;; All provided functions work on lists, strings and vectors.
35 ;; Functions taking a predicate or a function iterating over the
36 ;; sequence as argument take the function as their first argument and
37 ;; the sequence as their second argument. All other functions take
38 ;; the sequence as their first argument.
40 ;; All functions are tested in test/automated/seq-tests.el
44 (defmacro seq-doseq
(spec &rest body
)
45 "Loop over a sequence.
46 Similar to `dolist' but can be applied lists, strings and vectors.
48 Evaluate BODY with VAR bound to each element of SEQ, in turn.
49 Then evaluate RESULT to get return value, default nil.
51 \(fn (VAR SEQ [RESULT]) BODY...)"
52 (declare (indent 1) (debug ((symbolp form
&optional form
) body
)))
53 (let ((is-list (make-symbol "is-list"))
54 (seq (make-symbol "seq"))
55 (index (make-symbol "index")))
56 `(let* ((,seq
,(cadr spec
))
57 (,is-list
(listp ,seq
))
58 (,index
(if ,is-list
,seq
0)))
61 (< ,index
(seq-length ,seq
)))
62 (let ((,(car spec
) (if ,is-list
64 (seq-elt ,seq
,index
))))
66 (setq ,index
(if ,is-list
70 `((setq ,(car spec
) nil
) ,@(cddr spec
))))))
72 (defun seq-drop (seq n
)
73 "Return a subsequence of SEQ without its first N elements.
74 The result is a sequence of the same type as SEQ.
76 If N is a negative integer or zero, SEQ is returned."
80 (seq--drop-list seq n
)
81 (let ((length (seq-length seq
)))
82 (seq-subseq seq
(min n length
) length
)))))
84 (defun seq-take (seq n
)
85 "Return a subsequence of SEQ with its first N elements.
86 The result is a sequence of the same type as SEQ.
88 If N is a negative integer or zero, an empty sequence is
91 (seq--take-list seq n
)
92 (seq-subseq seq
0 (min (max n
0) (seq-length seq
)))))
94 (defun seq-drop-while (pred seq
)
95 "Return a sequence, from the first element for which (PRED element) is nil, of SEQ.
96 The result is a sequence of the same type as SEQ."
98 (seq--drop-while-list pred seq
)
99 (seq-drop seq
(seq--count-successive pred seq
))))
101 (defun seq-take-while (pred seq
)
102 "Return a sequence of the successive elements for which (PRED element) is non-nil in SEQ.
103 The result is a sequence of the same type as SEQ."
105 (seq--take-while-list pred seq
)
106 (seq-take seq
(seq--count-successive pred seq
))))
108 (defun seq-filter (pred seq
)
109 "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
110 (let ((exclude (make-symbol "exclude")))
111 (delq exclude
(seq-map (lambda (elt)
112 (if (funcall pred elt
)
117 (defun seq-remove (pred seq
)
118 "Return a list of all the elements for which (PRED element) is nil in SEQ."
119 (seq-filter (lambda (elt) (not (funcall pred elt
)))
122 (defun seq-reduce (function seq initial-value
)
123 "Reduce the function FUNCTION across SEQ, starting with INITIAL-VALUE.
125 Return the result of calling FUNCTION with INITIAL-VALUE and the
126 first element of SEQ, then calling FUNCTION with that result and
127 the second element of SEQ, then with that result and the third
130 If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
131 (if (seq-empty-p seq
)
133 (let ((acc initial-value
))
135 (setq acc
(funcall function acc elt
)))
138 (defun seq-some-p (pred seq
)
139 "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
142 (when (funcall pred elt
)
143 (throw 'seq--break elt
)))
146 (defun seq-every-p (pred seq
)
147 "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
150 (or (funcall pred elt
)
151 (throw 'seq--break nil
)))
154 (defun seq-count (pred seq
)
155 "Return the number of elements for which (PRED element) returns non-nil in seq."
158 (when (funcall pred elt
)
159 (setq count
(+ 1 count
))))
162 (defun seq-empty-p (seq)
163 "Return non-nil if the sequence SEQ is empty, nil otherwise."
166 (= 0 (seq-length seq
))))
168 (defun seq-sort (pred seq
)
169 "Return a sorted sequence comparing using PRED the elements of SEQ.
170 The result is a sequence of the same type as SEQ."
172 (sort (seq-copy seq
) pred
)
173 (let ((result (seq-sort pred
(append seq nil
))))
174 (cond ((stringp seq
) (concat result
))
175 ((vectorp seq
) (vconcat result
))
176 (t (error "Unsupported sequence: %s" seq
))))))
178 (defun seq-contains-p (seq elt
&optional testfn
)
179 "Return the first element in SEQ that equals to ELT.
180 Equality is defined by TESTFN if non-nil or by `equal' if nil."
181 (seq-some-p (lambda (e)
182 (funcall (or testfn
#'equal
) elt e
))
185 (defun seq-uniq (seq &optional testfn
)
186 "Return a list of the elements of SEQ with duplicates removed.
187 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
190 (unless (seq-contains-p result elt testfn
)
191 (setq result
(cons elt result
))))
194 (defun seq-subseq (seq start
&optional end
)
195 "Return the subsequence of SEQ from START to END.
196 If END is omitted, it defaults to the length of the sequence.
197 If START or END is negative, it counts from the end."
198 (cond ((or (stringp seq
) (vectorp seq
)) (substring seq start end
))
200 (let (len (errtext (format "Bad bounding indices: %s, %s" start end
)))
201 (and end
(< end
0) (setq end
(+ end
(setq len
(seq-length seq
)))))
202 (if (< start
0) (setq start
(+ start
(or len
(setq len
(seq-length seq
))))))
204 (setq seq
(nthcdr (1- start
) seq
))
205 (or seq
(error "%s" errtext
))
206 (setq seq
(cdr seq
)))
209 (while (and (>= (setq end
(1- end
)) start
) seq
)
210 (push (pop seq
) res
))
211 (or (= (1+ end
) start
) (error "%s" errtext
))
214 (t (error "Unsupported sequence: %s" seq
))))
216 (defun seq-concatenate (type &rest seqs
)
217 "Concatenate, into a sequence of type TYPE, the sequences SEQS.
218 TYPE must be one of following symbols: vector, string or list.
220 \n(fn TYPE SEQUENCE...)"
222 (`vector
(apply #'vconcat seqs
))
223 (`string
(apply #'concat seqs
))
224 (`list
(apply #'append
(append seqs
'(nil))))
225 (t (error "Not a sequence type name: %s" type
))))
227 (defun seq--drop-list (list n
)
228 "Optimized version of `seq-drop' for lists."
229 (while (and list
(> n
0))
230 (setq list
(cdr list
)
234 (defun seq--take-list (list n
)
235 "Optimized version of `seq-take' for lists."
237 (while (and list
(> n
0))
239 (push (pop list
) result
))
242 (defun seq--drop-while-list (pred list
)
243 "Optimized version of `seq-drop-while' for lists."
244 (while (and list
(funcall pred
(car list
)))
245 (setq list
(cdr list
)))
248 (defun seq--take-while-list (pred list
)
249 "Optimized version of `seq-take-while' for lists."
251 (while (and list
(funcall pred
(car list
)))
252 (push (pop list
) result
))
255 (defun seq--count-successive (pred seq
)
256 "Return the number of successive elements for which (PRED element) is non-nil in SEQ."
258 (len (seq-length seq
)))
259 (while (and (< n len
)
260 (funcall pred
(seq-elt seq n
)))
264 (defalias 'seq-copy
#'copy-sequence
)
265 (defalias 'seq-elt
#'elt
)
266 (defalias 'seq-reverse
#'reverse
)
267 (defalias 'seq-length
#'length
)
268 (defalias 'seq-do
#'mapc
)
269 (defalias 'seq-each
#'seq-do
)
270 (defalias 'seq-map
#'mapcar
)