code.delx.au - gnu-emacs/blob - lisp/emacs-lisp/seq.el

   1 ;;; seq.el --- Sequence manipulation functions  -*- lexical-binding: t -*-
   2
   3 ;; Copyright (C) 2014-2015 Free Software Foundation, Inc.
   4
   5 ;; Author: Nicolas Petton <nicolas@petton.fr>
   6 ;; Keywords: sequences
   7 ;; Version: 1.4
   8 ;; Package: seq
   9
  10 ;; Maintainer: emacs-devel@gnu.org
  11
  12 ;; This file is part of GNU Emacs.
  13
  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.
  18
  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.
  23
  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/>.
  26
  27 ;;; Commentary:
  28
  29 ;; Sequence-manipulation functions that complement basic functions
  30 ;; provided by subr.el.
  31 ;;
  32 ;; All functions are prefixed with "seq-".
  33 ;;
  34 ;; All provided functions work on lists, strings and vectors.
  35 ;;
  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.
  40 ;;
  41 ;; All functions are tested in test/automated/seq-tests.el
  42
  43 ;;; Code:
  44
  45 (defmacro seq-doseq (spec &rest body)
  46   "Loop over a sequence.
  47 Similar to `dolist' but can be applied to lists, strings, and vectors.
  48
  49 Evaluate BODY with VAR bound to each element of SEQ, in turn.
  50
  51 \(fn (VAR SEQ) 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             (,length (if (listp ,seq) nil (seq-length ,seq)))
  58             (,index (if ,is-list ,seq 0)))
  59        (while (if ,length
  60                   (< ,index ,length)
  61                 (consp ,index))
  62          (let ((,(car spec) (if ,length
  63                                 (prog1 (seq-elt ,seq ,index)
  64                                   (setq ,index (+ ,index 1)))
  65                               (pop ,index))))
  66            ,@body))
  67        ;; FIXME: Do we really want to support this?
  68        ,@(cddr spec))))
  69
  70 (defun seq-drop (seq n)
  71   "Return a subsequence of SEQ without its first N elements.
  72 The result is a sequence of the same type as SEQ.
  73
  74 If N is a negative integer or zero, SEQ is returned."
  75   (if (<= n 0)
  76       seq
  77     (if (listp seq)
  78         (seq--drop-list seq n)
  79       (let ((length (seq-length seq)))
  80         (seq-subseq seq (min n length) length)))))
  81
  82 (defun seq-take (seq n)
  83   "Return a subsequence of SEQ with its first N elements.
  84 The result is a sequence of the same type as SEQ.
  85
  86 If N is a negative integer or zero, an empty sequence is
  87 returned."
  88   (if (listp seq)
  89       (seq--take-list seq n)
  90     (seq-subseq seq 0 (min (max n 0) (seq-length seq)))))
  91
  92 (defun seq-drop-while (pred seq)
  93   "Return a sequence from the first element for which (PRED element) is nil in SEQ.
  94 The result is a sequence of the same type as SEQ."
  95   (if (listp seq)
  96       (seq--drop-while-list pred seq)
  97     (seq-drop seq (seq--count-successive pred seq))))
  98
  99 (defun seq-take-while (pred seq)
 100   "Return the successive elements for which (PRED element) is non-nil in SEQ.
 101 The result is a sequence of the same type as SEQ."
 102   (if (listp seq)
 103       (seq--take-while-list pred seq)
 104     (seq-take seq (seq--count-successive pred seq))))
 105
 106 (defun seq-filter (pred seq)
 107   "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
 108   (let ((exclude (make-symbol "exclude")))
 109     (delq exclude (seq-map (lambda (elt)
 110                              (if (funcall pred elt)
 111                                  elt
 112                                exclude))
 113                            seq))))
 114
 115 (defun seq-remove (pred seq)
 116   "Return a list of all the elements for which (PRED element) is nil in SEQ."
 117   (seq-filter (lambda (elt) (not (funcall pred elt)))
 118               seq))
 119
 120 (defun seq-reduce (function seq initial-value)
 121   "Reduce the function FUNCTION across SEQ, starting with INITIAL-VALUE.
 122
 123 Return the result of calling FUNCTION with INITIAL-VALUE and the
 124 first element of SEQ, then calling FUNCTION with that result and
 125 the second element of SEQ, then with that result and the third
 126 element of SEQ, etc.
 127
 128 If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
 129   (if (seq-empty-p seq)
 130       initial-value
 131     (let ((acc initial-value))
 132       (seq-doseq (elt seq)
 133         (setq acc (funcall function acc elt)))
 134       acc)))
 135
 136 (defun seq-some-p (pred seq)
 137   "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
 138   (catch 'seq--break
 139     (seq-doseq (elt seq)
 140       (when (funcall pred elt)
 141         (throw 'seq--break elt)))
 142     nil))
 143
 144 (defun seq-every-p (pred seq)
 145   "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
 146   (catch 'seq--break
 147     (seq-doseq (elt seq)
 148       (or (funcall pred elt)
 149           (throw 'seq--break nil)))
 150     t))
 151
 152 (defun seq-count (pred seq)
 153   "Return the number of elements for which (PRED element) is non-nil in SEQ."
 154   (let ((count 0))
 155     (seq-doseq (elt seq)
 156       (when (funcall pred elt)
 157         (setq count (+ 1 count))))
 158     count))
 159
 160 (defun seq-empty-p (seq)
 161   "Return non-nil if the sequence SEQ is empty, nil otherwise."
 162   (if (listp seq)
 163       (null seq)
 164     (= 0 (seq-length seq))))
 165
 166 (defun seq-sort (pred seq)
 167   "Return a sorted sequence comparing using PRED the elements of SEQ.
 168 The result is a sequence of the same type as SEQ."
 169   (if (listp seq)
 170       (sort (seq-copy seq) pred)
 171     (let ((result (seq-sort pred (append seq nil))))
 172       (seq-into result (type-of seq)))))
 173
 174 (defun seq-contains-p (seq elt &optional testfn)
 175   "Return the first element in SEQ that equals to ELT.
 176 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 177   (seq-some-p (lambda (e)
 178                 (funcall (or testfn #'equal) elt e))
 179               seq))
 180
 181 (defun seq-uniq (seq &optional testfn)
 182   "Return a list of the elements of SEQ with duplicates removed.
 183 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
 184   (let ((result '()))
 185     (seq-doseq (elt seq)
 186       (unless (seq-contains-p result elt testfn)
 187         (setq result (cons elt result))))
 188     (nreverse result)))
 189
 190 (defun seq-subseq (seq start &optional end)
 191   "Return the subsequence of SEQ from START to END.
 192 If END is omitted, it defaults to the length of the sequence.
 193 If START or END is negative, it counts from the end."
 194   (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
 195         ((listp seq)
 196          (let (len (errtext (format "Bad bounding indices: %s, %s" start end)))
 197            (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
 198            (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
 199            (when (> start 0)
 200              (setq seq (nthcdr (1- start) seq))
 201              (or seq (error "%s" errtext))
 202              (setq seq (cdr seq)))
 203            (if end
 204                (let ((res nil))
 205                  (while (and (>= (setq end (1- end)) start) seq)
 206                    (push (pop seq) res))
 207                  (or (= (1+ end) start) (error "%s" errtext))
 208                  (nreverse res))
 209              (seq-copy seq))))
 210         (t (error "Unsupported sequence: %s" seq))))
 211
 212 (defun seq-concatenate (type &rest seqs)
 213   "Concatenate, into a sequence of type TYPE, the sequences SEQS.
 214 TYPE must be one of following symbols: vector, string or list.
 215
 216 \n(fn TYPE SEQUENCE...)"
 217   (pcase type
 218     (`vector (apply #'vconcat seqs))
 219     (`string (apply #'concat seqs))
 220     (`list (apply #'append (append seqs '(nil))))
 221     (t (error "Not a sequence type name: %S" type))))
 222
 223 (defun seq-mapcat (function seq &optional type)
 224   "Concatenate the result of applying FUNCTION to each element of SEQ.
 225 The result is a sequence of type TYPE, or a list if TYPE is nil."
 226   (apply #'seq-concatenate (or type 'list)
 227          (seq-map function seq)))
 228
 229 (defun seq-partition (seq n)
 230   "Return a list of the elements of SEQ grouped into sub-sequences of length N.
 231 The last sequence may contain less than N elements.  If N is a
 232 negative integer or 0, nil is returned."
 233   (unless (< n 1)
 234     (let ((result '()))
 235       (while (not (seq-empty-p seq))
 236         (push (seq-take seq n) result)
 237         (setq seq (seq-drop seq n)))
 238       (nreverse result))))
 239
 240 (defun seq-intersection (seq1 seq2 &optional testfn)
 241   "Return a list of the elements that appear in both SEQ1 and SEQ2.
 242 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 243   (seq-reduce (lambda (acc elt)
 244                 (if (seq-contains-p seq2 elt testfn)
 245                     (cons elt acc)
 246                   acc))
 247               (seq-reverse seq1)
 248               '()))
 249
 250 (defun seq-difference (seq1 seq2 &optional testfn)
 251   "Return a list of th elements that appear in SEQ1 but not in SEQ2.
 252 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 253   (seq-reduce (lambda (acc elt)
 254                 (if (not (seq-contains-p seq2 elt testfn))
 255                     (cons elt acc)
 256                   acc))
 257               (seq-reverse seq1)
 258               '()))
 259
 260 (defun seq-group-by (function seq)
 261   "Apply FUNCTION to each element of SEQ.
 262 Separate the elements of SEQ into an alist using the results as
 263 keys.  Keys are compared using `equal'."
 264   (seq-reduce
 265    (lambda (acc elt)
 266      (let* ((key (funcall function elt))
 267             (cell (assoc key acc)))
 268        (if cell
 269            (setcdr cell (push elt (cdr cell)))
 270          (push (list key elt) acc))
 271        acc))
 272    (seq-reverse seq)
 273    nil))
 274
 275 (defalias 'seq-reverse
 276   (if (ignore-errors (reverse [1 2]))
 277       #'reverse
 278     (lambda (seq)
 279       "Return the reversed copy of list, vector, or string SEQ.
 280 See also the function `nreverse', which is used more often."
 281       (let ((result '()))
 282         (seq-map (lambda (elt) (push elt result))
 283                  seq)
 284         (if (listp seq)
 285             result
 286           (seq-into result (type-of seq)))))))
 287
 288 (defun seq-into (seq type)
 289   "Convert the sequence SEQ into a sequence of type TYPE.
 290 TYPE can be one of the following symbols: vector, string or list."
 291   (pcase type
 292     (`vector (vconcat seq))
 293     (`string (concat seq))
 294     (`list (append seq nil))
 295     (t (error "Not a sequence type name: %S" type))))
 296
 297 (defun seq--drop-list (list n)
 298   "Return a list from LIST without its first N elements.
 299 This is an optimization for lists in `seq-drop'."
 300   (while (and list (> n 0))
 301     (setq list (cdr list)
 302           n (1- n)))
 303   list)
 304
 305 (defun seq--take-list (list n)
 306   "Return a list from LIST made of its first N elements.
 307 This is an optimization for lists in `seq-take'."
 308   (let ((result '()))
 309     (while (and list (> n 0))
 310       (setq n (1- n))
 311       (push (pop list) result))
 312     (nreverse result)))
 313
 314 (defun seq--drop-while-list (pred list)
 315   "Return a list from the first element for which (PRED element) is nil in LIST.
 316 This is an optimization for lists in `seq-drop-while'."
 317   (while (and list (funcall pred (car list)))
 318     (setq list (cdr list)))
 319   list)
 320
 321 (defun seq--take-while-list (pred list)
 322   "Return the successive elements for which (PRED element) is non-nil in LIST.
 323 This is an optimization for lists in `seq-take-while'."
 324   (let ((result '()))
 325     (while (and list (funcall pred (car list)))
 326       (push (pop list) result))
 327     (nreverse result)))
 328
 329 (defun seq--count-successive (pred seq)
 330   "Return the number of successive elements for which (PRED element) is non-nil in SEQ."
 331   (let ((n 0)
 332         (len (seq-length seq)))
 333     (while (and (< n len)
 334                 (funcall pred (seq-elt seq n)))
 335       (setq n (+ 1 n)))
 336     n))
 337
 338 (defun seq--activate-font-lock-keywords ()
 339   "Activate font-lock keywords for some symbols defined in seq."
 340   (font-lock-add-keywords 'emacs-lisp-mode
 341                           '("\\<seq-doseq\\>")))
 342
 343 (defalias 'seq-copy #'copy-sequence)
 344 (defalias 'seq-elt #'elt)
 345 (defalias 'seq-length #'length)
 346 (defalias 'seq-do #'mapc)
 347 (defalias 'seq-each #'seq-do)
 348 (defalias 'seq-map #'mapcar)
 349
 350 (unless (fboundp 'elisp--font-lock-flush-elisp-buffers)
 351   ;; In Emacs≥25, (via elisp--font-lock-flush-elisp-buffers and a few others)
 352   ;; we automatically highlight macros.
 353   (add-to-list 'emacs-lisp-mode-hook #'seq--activate-font-lock-keywords))
 354
 355 (provide 'seq)
 356 ;;; seq.el ends here