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