code.delx.au - gnu-emacs-elpa/blob - packages/seq/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.9
   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 (pred seq)
 168   "Return non-nil if (PRED element) is non-nil for any element in SEQ, nil otherwise.
 169 If so, return the non-nil value returned by PRED."
 170   (catch 'seq--break
 171     (seq-doseq (elt seq)
 172       (let ((result (funcall pred elt)))
 173         (when result
 174           (throw 'seq--break result))))
 175     nil))
 176
 177 (defun seq-find (pred seq &optional default)
 178   "Return the first element for which (PRED element) is non-nil in SEQ.
 179 If no element is found, return DEFAULT.
 180
 181 Note that `seq-find' has an ambiguity if the found element is
 182 identical to DEFAULT, as it cannot be known if an element was
 183 found or not."
 184   (catch 'seq--break
 185     (seq-doseq (elt seq)
 186       (when (funcall pred elt)
 187         (throw 'seq--break elt)))
 188     default))
 189
 190 (defun seq-every-p (pred seq)
 191   "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
 192   (catch 'seq--break
 193     (seq-doseq (elt seq)
 194       (or (funcall pred elt)
 195           (throw 'seq--break nil)))
 196     t))
 197
 198 (defun seq-count (pred seq)
 199   "Return the number of elements for which (PRED element) is non-nil in SEQ."
 200   (let ((count 0))
 201     (seq-doseq (elt seq)
 202       (when (funcall pred elt)
 203         (setq count (+ 1 count))))
 204     count))
 205
 206 (defun seq-empty-p (seq)
 207   "Return non-nil if the sequence SEQ is empty, nil otherwise."
 208   (if (listp seq)
 209       (null seq)
 210     (= 0 (seq-length seq))))
 211
 212 (defun seq-sort (pred seq)
 213   "Return a sorted sequence comparing using PRED the elements of SEQ.
 214 The result is a sequence of the same type as SEQ."
 215   (if (listp seq)
 216       (sort (seq-copy seq) pred)
 217     (let ((result (seq-sort pred (append seq nil))))
 218       (seq-into result (type-of seq)))))
 219
 220 (defun seq-contains (seq elt &optional testfn)
 221   "Return the first element in SEQ that equals to ELT.
 222 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 223   (seq-some (lambda (e)
 224                 (funcall (or testfn #'equal) elt e))
 225               seq))
 226
 227 (defun seq-uniq (seq &optional testfn)
 228   "Return a list of the elements of SEQ with duplicates removed.
 229 TESTFN is used to compare elements, or `equal' if TESTFN is nil."
 230   (let ((result '()))
 231     (seq-doseq (elt seq)
 232       (unless (seq-contains result elt testfn)
 233         (setq result (cons elt result))))
 234     (nreverse result)))
 235
 236 (defun seq-subseq (seq start &optional end)
 237   "Return the subsequence of SEQ from START to END.
 238 If END is omitted, it defaults to the length of the sequence.
 239 If START or END is negative, it counts from the end."
 240   (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
 241         ((listp seq)
 242          (let (len (errtext (format "Bad bounding indices: %s, %s" start end)))
 243            (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
 244            (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
 245            (when (> start 0)
 246              (setq seq (nthcdr (1- start) seq))
 247              (or seq (error "%s" errtext))
 248              (setq seq (cdr seq)))
 249            (if end
 250                (let ((res nil))
 251                  (while (and (>= (setq end (1- end)) start) seq)
 252                    (push (pop seq) res))
 253                  (or (= (1+ end) start) (error "%s" errtext))
 254                  (nreverse res))
 255              (seq-copy seq))))
 256         (t (error "Unsupported sequence: %s" seq))))
 257
 258 (defun seq-concatenate (type &rest seqs)
 259   "Concatenate, into a sequence of type TYPE, the sequences SEQS.
 260 TYPE must be one of following symbols: vector, string or list.
 261
 262 \n(fn TYPE SEQUENCE...)"
 263   (pcase type
 264     (`vector (apply #'vconcat seqs))
 265     (`string (apply #'concat seqs))
 266     (`list (apply #'append (append seqs '(nil))))
 267     (t (error "Not a sequence type name: %S" type))))
 268
 269 (defun seq-mapcat (function seq &optional type)
 270   "Concatenate the result of applying FUNCTION to each element of SEQ.
 271 The result is a sequence of type TYPE, or a list if TYPE is nil."
 272   (apply #'seq-concatenate (or type 'list)
 273          (seq-map function seq)))
 274
 275 (defun seq-partition (seq n)
 276   "Return a list of the elements of SEQ grouped into sub-sequences of length N.
 277 The last sequence may contain less than N elements.  If N is a
 278 negative integer or 0, nil is returned."
 279   (unless (< n 1)
 280     (let ((result '()))
 281       (while (not (seq-empty-p seq))
 282         (push (seq-take seq n) result)
 283         (setq seq (seq-drop seq n)))
 284       (nreverse result))))
 285
 286 (defun seq-intersection (seq1 seq2 &optional testfn)
 287   "Return a list of the elements that appear in both SEQ1 and SEQ2.
 288 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 289   (seq-reduce (lambda (acc elt)
 290                 (if (seq-contains seq2 elt testfn)
 291                     (cons elt acc)
 292                   acc))
 293               (seq-reverse seq1)
 294               '()))
 295
 296 (defun seq-difference (seq1 seq2 &optional testfn)
 297   "Return a list of the elements that appear in SEQ1 but not in SEQ2.
 298 Equality is defined by TESTFN if non-nil or by `equal' if nil."
 299   (seq-reduce (lambda (acc elt)
 300                 (if (not (seq-contains seq2 elt testfn))
 301                     (cons elt acc)
 302                   acc))
 303               (seq-reverse seq1)
 304               '()))
 305
 306 (defun seq-group-by (function seq)
 307   "Apply FUNCTION to each element of SEQ.
 308 Separate the elements of SEQ into an alist using the results as
 309 keys.  Keys are compared using `equal'."
 310   (seq-reduce
 311    (lambda (acc elt)
 312      (let* ((key (funcall function elt))
 313             (cell (assoc key acc)))
 314        (if cell
 315            (setcdr cell (push elt (cdr cell)))
 316          (push (list key elt) acc))
 317        acc))
 318    (seq-reverse seq)
 319    nil))
 320
 321 (defalias 'seq-reverse
 322   (if (ignore-errors (reverse [1 2]))
 323       #'reverse
 324     (lambda (seq)
 325       "Return the reversed copy of list, vector, or string SEQ.
 326 See also the function `nreverse', which is used more often."
 327       (let ((result '()))
 328         (seq-map (lambda (elt) (push elt result))
 329                  seq)
 330         (if (listp seq)
 331             result
 332           (seq-into result (type-of seq)))))))
 333
 334 (defun seq-into (seq type)
 335   "Convert the sequence SEQ into a sequence of type TYPE.
 336 TYPE can be one of the following symbols: vector, string or list."
 337   (pcase type
 338     (`vector (vconcat seq))
 339     (`string (concat seq))
 340     (`list (append seq nil))
 341     (t (error "Not a sequence type name: %S" type))))
 342
 343 (defun seq-min (seq)
 344   "Return the smallest element of SEQ.
 345 SEQ must be a sequence of numbers or markers."
 346   (apply #'min (seq-into seq 'list)))
 347
 348 (defun seq-max (seq)
 349     "Return the largest element of SEQ.
 350 SEQ must be a sequence of numbers or markers."
 351   (apply #'max (seq-into seq 'list)))
 352
 353 (defun seq--drop-list (list n)
 354   "Return a list from LIST without its first N elements.
 355 This is an optimization for lists in `seq-drop'."
 356   (while (and list (> n 0))
 357     (setq list (cdr list)
 358           n (1- n)))
 359   list)
 360
 361 (defun seq--take-list (list n)
 362   "Return a list from LIST made of its first N elements.
 363 This is an optimization for lists in `seq-take'."
 364   (let ((result '()))
 365     (while (and list (> n 0))
 366       (setq n (1- n))
 367       (push (pop list) result))
 368     (nreverse result)))
 369
 370 (defun seq--drop-while-list (pred list)
 371   "Return a list from the first element for which (PRED element) is nil in LIST.
 372 This is an optimization for lists in `seq-drop-while'."
 373   (while (and list (funcall pred (car list)))
 374     (setq list (cdr list)))
 375   list)
 376
 377 (defun seq--take-while-list (pred list)
 378   "Return the successive elements for which (PRED element) is non-nil in LIST.
 379 This is an optimization for lists in `seq-take-while'."
 380   (let ((result '()))
 381     (while (and list (funcall pred (car list)))
 382       (push (pop list) result))
 383     (nreverse result)))
 384
 385 (defun seq--count-successive (pred seq)
 386   "Return the number of successive elements for which (PRED element) is non-nil in SEQ."
 387   (let ((n 0)
 388         (len (seq-length seq)))
 389     (while (and (< n len)
 390                 (funcall pred (seq-elt seq n)))
 391       (setq n (+ 1 n)))
 392     n))
 393
 394 (defun seq--make-pcase-bindings (args)
 395   "Return a list of bindings of the variables in ARGS to the elements of a sequence."
 396   (let ((bindings '())
 397         (index 0)
 398         (rest-marker nil))
 399     (seq-doseq (name args)
 400       (unless rest-marker
 401         (pcase name
 402           (`&rest
 403            (progn (push `(app (pcase--flip seq-drop ,index)
 404                               ,(seq--elt-safe args (1+ index)))
 405                         bindings)
 406                   (setq rest-marker t)))
 407           (t
 408            (push `(app (pcase--flip seq--elt-safe ,index) ,name) bindings))))
 409       (setq index (1+ index)))
 410     bindings))
 411
 412 (defun seq--make-pcase-patterns (args)
 413   "Return a list of `(seq ...)' pcase patterns from the argument list ARGS."
 414   (cons 'seq
 415         (seq-map (lambda (elt)
 416                    (if (seq-p elt)
 417                        (seq--make-pcase-patterns elt)
 418                      elt))
 419                  args)))
 420
 421 ;; Helper function for the Backward-compatible version of `seq-let'
 422 ;; for Emacs<25.1.
 423 (defun seq--make-bindings (args seq &optional bindings)
 424   "Return a list of bindings of the variables in ARGS to the elements of a sequence.
 425 if BINDINGS is non-nil, append new bindings to it, and return
 426 BINDINGS."
 427   (let ((index 0)
 428         (rest-marker nil))
 429     (seq-doseq (name args)
 430       (unless rest-marker
 431         (pcase name
 432           ((pred seq-p)
 433            (setq bindings (seq--make-bindings (seq--elt-safe args index)
 434                                               `(seq--elt-safe ,seq ,index)
 435                                               bindings)))
 436           (`&rest
 437            (progn (push `(,(seq--elt-safe args (1+ index))
 438                           (seq-drop ,seq ,index))
 439                         bindings)
 440                   (setq rest-marker t)))
 441           (t
 442            (push `(,name (seq--elt-safe ,seq ,index)) bindings))))
 443       (setq index (1+ index)))
 444     bindings))
 445
 446 (defun seq--elt-safe (seq n)
 447   "Return element of SEQ at the index N.
 448 If no element is found, return nil."
 449   (when (or (listp seq)
 450             (and (sequencep seq)
 451                  (> (seq-length seq) n)))
 452     (seq-elt seq n)))
 453
 454 (defun seq--activate-font-lock-keywords ()
 455   "Activate font-lock keywords for some symbols defined in seq."
 456   (font-lock-add-keywords 'emacs-lisp-mode
 457                           '("\\<seq-doseq\\>" "\\<seq-let\\>")))
 458
 459 (defalias 'seq-copy #'copy-sequence)
 460 (defalias 'seq-elt #'elt)
 461 (defalias 'seq-length #'length)
 462 (defalias 'seq-do #'mapc)
 463 (defalias 'seq-each #'seq-do)
 464 (defalias 'seq-map #'mapcar)
 465 (defalias 'seq-p #'sequencep)
 466
 467 (unless (fboundp 'elisp--font-lock-flush-elisp-buffers)
 468   ;; In Emacs≥25, (via elisp--font-lock-flush-elisp-buffers and a few others)
 469   ;; we automatically highlight macros.
 470   (add-hook 'emacs-lisp-mode-hook #'seq--activate-font-lock-keywords))
 471
 472 (provide 'seq)
 473 ;;; seq.el ends here