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.7
   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 ((length (make-symbol "length"))
  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 ,length 0 ,seq)))
  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
  68 (if (fboundp 'pcase-defmacro)
  69     ;; Implementation of `seq-let' based on a `pcase'
  70     ;; pattern. Requires Emacs>=25.1.
  71     (progn
  72       (pcase-defmacro seq (&rest args)
  73         "pcase pattern matching sequence elements.
  74 Matches if the object is a sequence (list, string or vector), and
  75 binds each element of ARGS to the corresponding element of the
  76 sequence."
  77         `(and (pred seq-p)
  78               ,@(seq--make-pcase-bindings args)))
  79
  80       (defmacro seq-let (args seq &rest body)
  81         "Bind the variables in ARGS to the elements of SEQ then evaluate BODY.
  82
  83 ARGS can also include the `&rest' marker followed by a variable
  84 name to be bound to the rest of SEQ."
  85         (declare (indent 2) (debug t))
  86         `(pcase-let ((,(seq--make-pcase-patterns args) ,seq))
  87            ,@body)))
  88
  89   ;; Implementation of `seq-let' compatible with Emacs<25.1.
  90   (defmacro seq-let (args seq &rest body)
  91     "Bind the variables in ARGS to the elements of SEQ then evaluate BODY.
  92
  93 ARGS can also include the `&rest' marker followed by a variable
  94 name to be bound to the rest of SEQ."
  95     (declare (indent 2) (debug t))
  96     (let ((seq-var (make-symbol "seq")))
  97       `(let* ((,seq-var ,seq)
  98               ,@(seq--make-bindings args seq-var))
  99          ,@body))))
 100
 101 (defun seq-drop (seq n)
 102   "Return a subsequence of SEQ without its first N elements.
 103 The result is a sequence of the same type as SEQ.
 104
 105 If N is a negative integer or zero, SEQ is returned."
 106   (if (<= n 0)
 107       seq
 108     (if (listp seq)
 109         (seq--drop-list seq n)
 110       (let ((length (seq-length seq)))
 111         (seq-subseq seq (min n length) length)))))
 112
 113 (defun seq-take (seq n)
 114   "Return a subsequence of SEQ with its first N elements.
 115 The result is a sequence of the same type as SEQ.
 116
 117 If N is a negative integer or zero, an empty sequence is
 118 returned."
 119   (if (listp seq)
 120       (seq--take-list seq n)
 121     (seq-subseq seq 0 (min (max n 0) (seq-length seq)))))
 122
 123 (defun seq-drop-while (pred seq)
 124   "Return a sequence from the first element for which (PRED element) is nil in SEQ.
 125 The result is a sequence of the same type as SEQ."
 126   (if (listp seq)
 127       (seq--drop-while-list pred seq)
 128     (seq-drop seq (seq--count-successive pred seq))))
 129
 130 (defun seq-take-while (pred seq)
 131   "Return the successive elements for which (PRED element) is non-nil in SEQ.
 132 The result is a sequence of the same type as SEQ."
 133   (if (listp seq)
 134       (seq--take-while-list pred seq)
 135     (seq-take seq (seq--count-successive pred seq))))
 136
 137 (defun seq-filter (pred seq)
 138   "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
 139   (let ((exclude (make-symbol "exclude")))
 140     (delq exclude (seq-map (lambda (elt)
 141                              (if (funcall pred elt)
 142                                  elt
 143                                exclude))
 144                            seq))))
 145
 146 (defun seq-remove (pred seq)
 147   "Return a list of all the elements for which (PRED element) is nil in SEQ."
 148   (seq-filter (lambda (elt) (not (funcall pred elt)))
 149               seq))
 150
 151 (defun seq-reduce (function seq initial-value)
 152   "Reduce the function FUNCTION across SEQ, starting with INITIAL-VALUE.
 153
 154 Return the result of calling FUNCTION with INITIAL-VALUE and the
 155 first element of SEQ, then calling FUNCTION with that result and
 156 the second element of SEQ, then with that result and the third
 157 element of SEQ, etc.
 158
 159 If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
 160   (if (seq-empty-p seq)
 161       initial-value
 162     (let ((acc initial-value))
 163       (seq-doseq (elt seq)
 164         (setq acc (funcall function acc elt)))
 165       acc)))
 166
 167 (defun seq-some-p (pred seq)
 168   "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
 169   (catch 'seq--break
 170     (seq-doseq (elt seq)
 171       (when (funcall pred elt)
 172         (throw 'seq--break elt)))
 173     nil))
 174
 175 (defun seq-every-p (pred seq)
 176   "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
 177   (catch 'seq--break
 178     (seq-doseq (elt seq)
 179       (or (funcall pred elt)
 180           (throw 'seq--break nil)))
 181     t))
 182
 183 (defun seq-count (pred seq)
 184   "Return the number of elements for which (PRED element) is non-nil in SEQ."
 185   (let ((count 0))
 186     (seq-doseq (elt seq)
 187       (when (funcall pred elt)
 188         (setq count (+ 1 count))))
 189     count))
 190
 191 (defun seq-empty-p (seq)
 192   "Return non-nil if the sequence SEQ is empty, nil otherwise."
 193   (if (listp seq)
 194       (null seq)
 195     (= 0 (seq-length seq))))
 196
 197 (defun seq-sort (pred seq)
 198   "Return a sorted sequence comparing using PRED the elements of SEQ.
 199 The result is a sequence of the same type as SEQ."
 200   (if (listp seq)
 201       (sort (seq-copy seq) pred)
 202     (let ((result (seq-sort pred (append seq nil))))
 203       (seq-into result (type-of seq)))))
 204
 205 (defun seq-contains-p (seq elt &optional testfn)
 206   "Return the first element in SEQ that equals to ELT.
 207 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 208   (seq-some-p (lambda (e)
 209                 (funcall (or testfn #'equal) elt e))
 210               seq))
 211
 212 (defun seq-uniq (seq &optional testfn)
 213   "Return a list of the elements of SEQ with duplicates removed.
 214 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
 215   (let ((result '()))
 216     (seq-doseq (elt seq)
 217       (unless (seq-contains-p result elt testfn)
 218         (setq result (cons elt result))))
 219     (nreverse result)))
 220
 221 (defun seq-subseq (seq start &optional end)
 222   "Return the subsequence of SEQ from START to END.
 223 If END is omitted, it defaults to the length of the sequence.
 224 If START or END is negative, it counts from the end."
 225   (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
 226         ((listp seq)
 227          (let (len (errtext (format "Bad bounding indices: %s, %s" start end)))
 228            (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
 229            (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
 230            (when (> start 0)
 231              (setq seq (nthcdr (1- start) seq))
 232              (or seq (error "%s" errtext))
 233              (setq seq (cdr seq)))
 234            (if end
 235                (let ((res nil))
 236                  (while (and (>= (setq end (1- end)) start) seq)
 237                    (push (pop seq) res))
 238                  (or (= (1+ end) start) (error "%s" errtext))
 239                  (nreverse res))
 240              (seq-copy seq))))
 241         (t (error "Unsupported sequence: %s" seq))))
 242
 243 (defun seq-concatenate (type &rest seqs)
 244   "Concatenate, into a sequence of type TYPE, the sequences SEQS.
 245 TYPE must be one of following symbols: vector, string or list.
 246
 247 \n(fn TYPE SEQUENCE...)"
 248   (pcase type
 249     (`vector (apply #'vconcat seqs))
 250     (`string (apply #'concat seqs))
 251     (`list (apply #'append (append seqs '(nil))))
 252     (t (error "Not a sequence type name: %S" type))))
 253
 254 (defun seq-mapcat (function seq &optional type)
 255   "Concatenate the result of applying FUNCTION to each element of SEQ.
 256 The result is a sequence of type TYPE, or a list if TYPE is nil."
 257   (apply #'seq-concatenate (or type 'list)
 258          (seq-map function seq)))
 259
 260 (defun seq-partition (seq n)
 261   "Return a list of the elements of SEQ grouped into sub-sequences of length N.
 262 The last sequence may contain less than N elements.  If N is a
 263 negative integer or 0, nil is returned."
 264   (unless (< n 1)
 265     (let ((result '()))
 266       (while (not (seq-empty-p seq))
 267         (push (seq-take seq n) result)
 268         (setq seq (seq-drop seq n)))
 269       (nreverse result))))
 270
 271 (defun seq-intersection (seq1 seq2 &optional testfn)
 272   "Return a list of the elements that appear in both SEQ1 and SEQ2.
 273 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 274   (seq-reduce (lambda (acc elt)
 275                 (if (seq-contains-p seq2 elt testfn)
 276                     (cons elt acc)
 277                   acc))
 278               (seq-reverse seq1)
 279               '()))
 280
 281 (defun seq-difference (seq1 seq2 &optional testfn)
 282   "Return a list of th elements that appear in SEQ1 but not in SEQ2.
 283 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 284   (seq-reduce (lambda (acc elt)
 285                 (if (not (seq-contains-p seq2 elt testfn))
 286                     (cons elt acc)
 287                   acc))
 288               (seq-reverse seq1)
 289               '()))
 290
 291 (defun seq-group-by (function seq)
 292   "Apply FUNCTION to each element of SEQ.
 293 Separate the elements of SEQ into an alist using the results as
 294 keys.  Keys are compared using `equal'."
 295   (seq-reduce
 296    (lambda (acc elt)
 297      (let* ((key (funcall function elt))
 298             (cell (assoc key acc)))
 299        (if cell
 300            (setcdr cell (push elt (cdr cell)))
 301          (push (list key elt) acc))
 302        acc))
 303    (seq-reverse seq)
 304    nil))
 305
 306 (defalias 'seq-reverse
 307   (if (ignore-errors (reverse [1 2]))
 308       #'reverse
 309     (lambda (seq)
 310       "Return the reversed copy of list, vector, or string SEQ.
 311 See also the function `nreverse', which is used more often."
 312       (let ((result '()))
 313         (seq-map (lambda (elt) (push elt result))
 314                  seq)
 315         (if (listp seq)
 316             result
 317           (seq-into result (type-of seq)))))))
 318
 319 (defun seq-into (seq type)
 320   "Convert the sequence SEQ into a sequence of type TYPE.
 321 TYPE can be one of the following symbols: vector, string or list."
 322   (pcase type
 323     (`vector (vconcat seq))
 324     (`string (concat seq))
 325     (`list (append seq nil))
 326     (t (error "Not a sequence type name: %S" type))))
 327
 328 (defun seq--drop-list (list n)
 329   "Return a list from LIST without its first N elements.
 330 This is an optimization for lists in `seq-drop'."
 331   (while (and list (> n 0))
 332     (setq list (cdr list)
 333           n (1- n)))
 334   list)
 335
 336 (defun seq--take-list (list n)
 337   "Return a list from LIST made of its first N elements.
 338 This is an optimization for lists in `seq-take'."
 339   (let ((result '()))
 340     (while (and list (> n 0))
 341       (setq n (1- n))
 342       (push (pop list) result))
 343     (nreverse result)))
 344
 345 (defun seq--drop-while-list (pred list)
 346   "Return a list from the first element for which (PRED element) is nil in LIST.
 347 This is an optimization for lists in `seq-drop-while'."
 348   (while (and list (funcall pred (car list)))
 349     (setq list (cdr list)))
 350   list)
 351
 352 (defun seq--take-while-list (pred list)
 353   "Return the successive elements for which (PRED element) is non-nil in LIST.
 354 This is an optimization for lists in `seq-take-while'."
 355   (let ((result '()))
 356     (while (and list (funcall pred (car list)))
 357       (push (pop list) result))
 358     (nreverse result)))
 359
 360 (defun seq--count-successive (pred seq)
 361   "Return the number of successive elements for which (PRED element) is non-nil in SEQ."
 362   (let ((n 0)
 363         (len (seq-length seq)))
 364     (while (and (< n len)
 365                 (funcall pred (seq-elt seq n)))
 366       (setq n (+ 1 n)))
 367     n))
 368
 369 (defun seq--make-pcase-bindings (args)
 370   "Return a list of bindings of the variables in ARGS to the elements of a sequence."
 371   (let ((bindings '())
 372         (index 0)
 373         (rest-marker nil))
 374     (seq-doseq (name args)
 375       (unless rest-marker
 376         (pcase name
 377           (`&rest
 378            (progn (push `(app (pcase--flip seq-drop ,index)
 379                               ,(seq--elt-safe args (1+ index)))
 380                         bindings)
 381                   (setq rest-marker t)))
 382           (t
 383            (push `(app (pcase--flip seq--elt-safe ,index) ,name) bindings))))
 384       (setq index (1+ index)))
 385     bindings))
 386
 387 (defun seq--make-pcase-patterns (args)
 388   "Return a list of `(seq ...)' pcase patterns from the argument list ARGS."
 389   (cons 'seq
 390         (seq-map (lambda (elt)
 391                    (if (seq-p elt)
 392                        (seq--make-pcase-patterns elt)
 393                      elt))
 394                  args)))
 395
 396 ;; Helper function for the Backward-compatible version of `seq-let'
 397 ;; for Emacs<25.1.
 398 (defun seq--make-bindings (args seq &optional bindings)
 399   "Return a list of bindings of the variables in ARGS to the elements of a sequence.
 400 if BINDINGS is non-nil, append new bindings to it, and return
 401 BINDINGS."
 402   (let ((index 0)
 403         (rest-marker nil))
 404     (seq-doseq (name args)
 405       (unless rest-marker
 406         (pcase name
 407           ((pred seq-p)
 408            (setq bindings (seq--make-bindings (seq--elt-safe args index)
 409                                               `(seq--elt-safe ,seq ,index)
 410                                               bindings)))
 411           (`&rest
 412            (progn (push `(,(seq--elt-safe args (1+ index))
 413                           (seq-drop ,seq ,index))
 414                         bindings)
 415                   (setq rest-marker t)))
 416           (t
 417            (push `(,name (seq--elt-safe ,seq ,index)) bindings))))
 418       (setq index (1+ index)))
 419     bindings))
 420
 421 (defun seq--elt-safe (seq n)
 422   "Return element of SEQ at the index N.
 423 If no element is found, return nil."
 424   (when (or (listp seq)
 425             (and (sequencep seq)
 426                  (> (seq-length seq) n)))
 427     (seq-elt seq n)))
 428
 429 (defun seq--activate-font-lock-keywords ()
 430   "Activate font-lock keywords for some symbols defined in seq."
 431   (font-lock-add-keywords 'emacs-lisp-mode
 432                           '("\\<seq-doseq\\>" "\\<seq-let\\>")))
 433
 434 (defalias 'seq-copy #'copy-sequence)
 435 (defalias 'seq-elt #'elt)
 436 (defalias 'seq-length #'length)
 437 (defalias 'seq-do #'mapc)
 438 (defalias 'seq-each #'seq-do)
 439 (defalias 'seq-map #'mapcar)
 440 (defalias 'seq-p #'sequencep)
 441
 442 (unless (fboundp 'elisp--font-lock-flush-elisp-buffers)
 443   ;; In Emacs≥25, (via elisp--font-lock-flush-elisp-buffers and a few others)
 444   ;; we automatically highlight macros.
 445   (add-hook 'emacs-lisp-mode-hook #'seq--activate-font-lock-keywords))
 446
 447 (provide 'seq)
 448 ;;; seq.el ends here