sequence manipulation functions

sequence manipulation functions

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 94 bytes --]

Hi!

Here are two files that add some missing sequence-manipulation functions
to Emacs Lisp.


[-- Attachment #2: sequences.el --]
[-- Type: text/plain, Size: 4277 bytes --]

;;; sequences.el --- Sequence manipulation functions  -*- lexical-binding: t -*-

;; Copyright (C) 2014 Free Software Foundation, Inc.

;; Author: Nicolas Petton <petton.nicolas@gmail.com>
;; Keywords: sequences

;; Maintainer: emacs-devel@gnu.org

;; This file is part of GNU Emacs.

;; GNU Emacs is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; GNU Emacs is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.

;;; Commentary:

;; Sequence manipulation functions

;;; Code:

;;;###autoload
(defun first (seq)
  "Return the first element of the sequence SEQ.
If SEQ is nil or empty, return nil."
  (if (listp seq)
      (car seq)
    (when (not (empty-p seq))
      (elt seq 0))))

;;;###autoload
(defun rest (seq)
  "Return all but the first element of the sequence SEQ.
If SEQ is nil or empty, return nil."
  (if (listp seq)
      (cdr seq)
    (when (not (empty-p seq))
      (drop 1 seq))))

;;;###autoload
(defun drop (n seq)
  "Return a subsequence, without its first N items, of the sequence SEQ."
  (let ((length (length seq)))
    (subseq seq (min n length) length)))

;;;###autoload
(defun take (n seq)
  "Return a sequence of the first N items of SEQ."
  (subseq seq 0 (min n (length seq))))

;;;###autoload
(defun filter (pred seq)
  "Return a list filtering with PRED all items of SEQ."
  (delq nil (mapcar (lambda (elt)
                      (and (funcall pred elt) elt))
                    seq)))

;;;###autoload
(defun reduce (function seq &optional initial-value)
  "Reduce two-argument FUNCTION across SEQ, starting with INITIAL-VALUE if not nil."
  (let ((acc (or initial-value (if (empty-p seq)
                                   (funcall function)
                                 (first seq)))))
    (mapc (lambda (item)
            (setq acc (funcall function acc item)))
          (if initial-value seq (rest seq)))
    acc))

;;;###autoload
(defun some-p (pred seq)
  "Return any element for which PRED is true in SEQ, nil otherwise."
  (car (filter pred seq)))

;;;###autoload
(defun every-p (pred seq)
  "Return t if (PRED item) is non-nil for all items of the sequence SEQ."
  (catch 'break
    (mapc (lambda (elt)
            (or (funcall pred elt) (throw 'break nil)))
          seq)
    t))

;;;###autoload
(defun empty-p (seq)
  "Return t if the sequence SEQ is empty, nil otherwise."
  (= 0 (length seq)))

;;;###autoload
(defun sort-seq (seq pred)
  "Sort the sequence SEQ comparing elements using PRED."
  (if (listp seq)
      (sort (copy-seq seq) pred)
    (sort-seq (append seq nil) pred)))

(defalias 'copy-seq #'copy-sequence)

;;;###autoload
(defun subseq (seq start &optional end)
  "Return the subsequence of SEQ from START to END.
If END is omitted, it defaults to the length of the sequence.
If START or END is negative, it counts from the end."
  (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
        ((listp seq)
         (let (len)
           (and end (< end 0) (setq end (+ end (setq len (length seq)))))
           (if (< start 0) (setq start (+ start (or len (setq len (length seq))))))
           (if (> start 0) (setq seq (nthcdr start seq)))
           (if end
               (let ((res nil))
                 (while (>= (setq end (1- end)) start)
                   (push (pop seq) res))
                 (nreverse res))
             (copy-sequence seq))))
        (t (error "Unsupported sequence: %s" seq))))

;;;###autoload
(defun concatenate (type &rest seqs)
  "Concatenate, into a sequence of type TYPE, the argument SEQS.
\n(fn TYPE SEQUENCE...)"
  (pcase type
    (`vector (apply #'vconcat seqs))
    (`string (apply #'concat seqs))
    (`list (apply #'append (append seqs '(nil))))
    (t (error "Not a sequence type name: %s" type))))

(provide 'sequences)
;;; sequences.el ends here

[-- Attachment #3: sequences-tests.el --]
[-- Type: text/plain, Size: 5323 bytes --]

;;; sequences-tests.el --- Tests for sequences.el

;; Copyright (C) 2014 Free Software Foundation, Inc.

;; Author: Nicolas Petton <petton.nicolas@gmail.com>
;; Maintainer: emacs-devel@gnu.org

;; This file is part of GNU Emacs.

;; GNU Emacs is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;; GNU Emacs is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.

;;; Commentary:

;; Tests for sequences.el

;;; Code:

(require 'ert)
(require 'sequences)

(defmacro with-test-sequences (spec &rest body)
  "Successively bind VAR to a list, vector, and string built from SEQ.
Evaluate BODY for each created sequence.

\(fn (var seq) body)"
  (declare (indent 1) (debug ((symbolp form) body)))
  (let ((initial-seq (make-symbol "initial-seq")))
    `(let ((,initial-seq ,(cadr spec))) 
       ,@(mapcar (lambda (s)
                   `(let ((,(car spec) (apply (function ,s) ,initial-seq)))
                      ,@body))
                 '(list vector string)))))

(defun same-contents-p (seq1 seq2)
  "Return t if SEQ1 and SEQ2 have the same contents, nil otherwise."
  (equal (append seq1 '()) (append seq2 '())))

(ert-deftest test-sequences-first ()
  (with-test-sequences (seq '(2 4 6))
    (should (= (first seq) 2)))
  (with-test-sequences (seq '())
    (should (eq (first seq) nil))))

(ert-deftest test-sequences-rest ()
  (with-test-sequences (seq '(2 4 6))
    (should (same-contents-p (rest seq) '(4 6))))
  (with-test-sequences (seq '())
    (should (eq (rest seq) nil))))

(ert-deftest test-sequences-drop ()
  (with-test-sequences (seq '(1 2 3 4))
    (should (equal (drop 0 seq) seq))
    (should (equal (drop 1 seq) (rest seq)))
    (should (equal (drop 2 seq) (rest (rest seq))))
    (should (empty-p (drop 4 seq)))
    (should (empty-p (drop 10 seq))))
  (with-test-sequences (seq '())
    (should (empty-p (drop 0 seq)))
    (should (empty-p (drop 1 seq)))))

(ert-deftest test-sequences-take ()
  (with-test-sequences (seq '(2 3 4 5))
    (should (empty-p (take 0 seq)))
    (should (= (length (take 1 seq)) 1))
    (should (= (first (take 1 seq)) 2))
    (should (same-contents-p (take 3 seq) '(2 3 4)))
    (should (equal (take 10 seq) seq))))

(ert-deftest test-sequences-filter ()
  (with-test-sequences (seq '(6 7 8 9 10))
    (should (equal (filter #'evenp seq) '(6 8 10)))
    (should (equal (filter #'oddp seq) '(7 9)))
    (should (equal (filter (lambda (elt) nil) seq) '())))
  (with-test-sequences (seq '())
    (should (equal (filter #'evenp seq) '()))))

(ert-deftest test-sequences-reduce ()
  (with-test-sequences (seq '(1 2 3 4))
    (should (= (reduce #'+ seq) 10))
    (should (= (reduce #'+ seq 5) 15)))
  (with-test-sequences (seq '())
    (should (eq (reduce #'+ seq) 0))
    (should (eq (reduce #'+ seq 7) 7))))

(ert-deftest test-sequences-some-p ()
  (with-test-sequences (seq '(4 3 2 1))
    (should (= (some-p #'evenp seq) 4))
    (should (= (some-p #'oddp seq) 3))
    (should-not (some-p (lambda (elt) (> elt 10)) seq)))
  (with-test-sequences (seq '())
    (should-not (some-p #'oddp seq))))

(ert-deftest test-sequences-every-p ()
  (with-test-sequences (seq '(43 54 22 1))
    (should (every-p (lambda (elt) t) seq))
    (should-not (every-p #'oddp seq))
    (should-not (every-p #'evenp seq)))
  (with-test-sequences (seq '(42 54 22 2))
    (should (every-p #'evenp seq))
    (should-not (every-p #'oddp seq)))
  (with-test-sequences (seq '())
    (should (every-p #'identity seq))
    (should (every-p #'evenp seq))))

(ert-deftest test-sequences-empty-p ()
  (with-test-sequences (seq '(0))
    (should-not (empty-p seq)))
  (with-test-sequences (seq '(0 1 2))
    (should-not (empty-p seq)))
  (with-test-sequences (seq '())
    (should (empty-p seq))))

(ert-deftest test-sequences-sort-seq ()
  (with-test-sequences (seq '(89 32 12 3 5 1 1))
    (should (equal (sort-seq seq #'<) '(1 1 3 5 12 32 89))))
  (with-test-sequences (seq '())
    (should (equal (sort-seq seq #'<) '()))))

(ert-deftest test-sequences-subseq ()
  (with-test-sequences (seq '(2 3 4 5))
    (should (equal (subseq seq 0 4) seq))
    (should (equal (subseq seq 2 4) (rest (rest seq))))
    (should (same-contents-p (subseq seq 1 3) '(3 4)))
    (should (same-contents-p (subseq seq 1 -1) '(3 4))))
  (should (vectorp (subseq [2 3 4 5] 2)))
  (should (stringp (subseq "foo" 2 3)))
  (should (listp (subseq '(2 3 4 4) 2 3))))

(ert-deftest test-sequences-concatenate ()
  (with-test-sequences (seq '(2 4 6))
    (should (equal (concatenate 'string seq [8]) (string 2 4 6 8)))
    (should (equal (concatenate 'list seq '(8 10)) '(2 4 6 8 10)))
    (should (equal (concatenate 'vector seq '(8 10)) [2 4 6 8 10]))
    (should (equal (concatenate 'vector nil '(8 10)) [8 10]))
    (should (equal (concatenate 'vector seq nil) [2 4 6]))))

(provide 'sequences-tests)
;;; sequences-tests.el ends here

[-- Attachment #4: Type: text/plain, Size: 964 bytes --]



It provides:

- coherent naming that fits well with existing sequence functions
- all functions work on lists, vectors and strings
- consistency:
  - all mapping functions take the sequence as their second argument
  - other sequence functions take the sequence as their their first
    argument
- all functions are documented
- all functions are tested

It adds the following functions: "first", "rest", "take", "drop",
"filter", "reduce", "some-p", "every-p", "empty-p", "sort-seq", "subseq"
and "concatenate". Together with existing mapping and other
sequence-manipulation functions I think it provides a good library. I
probably missed some though.

If you are interested, I'd like to have feedback on this, and I'm also
willing to update the documentation for sequences and send a proper
patch.

As I don't know what is the best way to submit a patch to Emacs, I
simply attached both elisp files. 


Cheers,
Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Glenn Morris]

Nicolas Petton wrote:

> ;; Copyright (C) 2014 Free Software Foundation, Inc.
[...]
> ;; Maintainer: emacs-devel@gnu.org
[...]
> ;; This file is part of GNU Emacs.

Thanks; but just to nitpick none of the above are true.
They might be true in future of course, but till then best not to
confuse people.

Re: sequence manipulation functions

[Nicolas Petton]

Glenn Morris <rgm@gnu.org> writes:

> Nicolas Petton wrote:
>
>> ;; Copyright (C) 2014 Free Software Foundation, Inc.
> [...]
>> ;; Maintainer: emacs-devel@gnu.org
> [...]
>> ;; This file is part of GNU Emacs.
>
> Thanks; but just to nitpick none of the above are true.
> They might be true in future of course, but till then best not to
> confuse people.

Indeed, you are right. I initially planned to send a patch against Emacs
trunk, that's why I wrote the header like this.

Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

This library has the same problem as cl: it defines functions
which don't have a name prefix, and are therefore liable to conflict
with users' own functions.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.

Re: sequence manipulation functions

[Nicolas Petton]

Richard Stallman <rms@gnu.org> writes:

> [[[ To any NSA and FBI agents reading my email: please consider    ]]]
> [[[ whether defending the US Constitution against all enemies,     ]]]
> [[[ foreign or domestic, requires you to follow Snowden's example. ]]]
>
> This library has the same problem as cl: it defines functions
> which don't have a name prefix, and are therefore liable to conflict
> with users' own functions.

Hi,

My goal was to add these functions as core sequence-manipulation
functions to Elisp, not an optional library. I didn't add a prefix on
purpose, as "elt", "remove", etc. sequence-manipulation functions are
not prefixed.

Regards,
Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 564 bytes --]

On 11/05/2014 04:58 AM, Richard Stallman wrote:
> This library has the same problem as cl: it defines functions
> which don't have a name prefix, and are therefore liable to conflict
> with users' own functions.

I've never been particularly receptive to that line of thinking. Who's
to say that our chosen prefixes won't conflict with user functions?
Requiring some unlikely prefix for all future additions to the Emacs
core is too burdensome a requirement.

Then again, I thought we should merge cl-lib without the cl- prefix, but
I lost that one.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: sequence manipulation functions

[Damien Cassou]

On Tue, Nov 4, 2014 at 11:17 PM, Nicolas Petton
<petton.nicolas@gmail.com> wrote:
> Here are two files that add some missing sequence-manipulation functions
> to Emacs Lisp.


I like them a lot and would like them to be included in Emacs.


On Wed, Nov 5, 2014 at 5:58 AM, Richard Stallman <rms@gnu.org> wrote:
> This library has the same problem as cl: it defines functions
> which don't have a name prefix, and are therefore liable to conflict
> with users' own functions.

Isn't that the case of all functions that are added to Emacs? For
example, Emacs 24.4 features quite some new functions including
`file-acl', `set-file-acl', `display-monitor-attributes-list',
`frame-monitor-attributes', `window-scroll-bar-width',
`special-form-p', `macrop', `with-eval-after-load', `group-gid',
`get-pos-property'.

Are you saying that all these functions have a reserved prefix (file,
set, display, special, get, group, with)? What about macrop?

Each time Emacs features a new function/macro/variable, there is a
risk of conflict with users' own functions. Still, Emacs maintainers
add these features because they simplify the life for everyone.

I vote for including these functions.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm."
Winston Churchill

Re: sequence manipulation functions

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > > This library has the same problem as cl: it defines functions
  > > which don't have a name prefix, and are therefore liable to conflict
  > > with users' own functions.

  > Isn't that the case of all functions that are added to Emacs?

Not all.  Several of the examples you cited have a name prefix which
makes conflicts unlikely.

When the issue is to add a function to Emacs _as a documented
function_, something that is part of the name space users should not
know about and not interfere with, a name prefix is not necessary.

However, the message I responded to did not talk about adding
documented standard functions to Emacs.  It proposed a library that
could be loaded.  That is a different kind of issue.


-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.

Re: sequence manipulation functions

[Nicolas Petton]

Richard Stallman <rms@gnu.org> writes:
> However, the message I responded to did not talk about adding
> documented standard functions to Emacs.  It proposed a library that
> could be loaded.  That is a different kind of issue.

That's not what I meant but it's my fault. I should probably have added
these functions to subr.el or subr-x.el and sent a patch with the
documentation updated. I didn't stress enough that I wanted to add
documented standard functions to Emacs.

But as Stefan suggested, I'm rewriting it with "seq-" as a prefix. It
makes sense for several reasons. Also, I compared it with the new
string-manipulation functions in subr-x.el, and they all use "string-"
as a prefix.

Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Stefan Monnier]

> That's not what I meant but it's my fault. I should probably have added
> these functions to subr.el or subr-x.el and sent a patch with the
> documentation updated. I didn't stress enough that I wanted to add
> documented standard functions to Emacs.

No, these should stay in a separate file.  subr.el is much too
large already.


        Stefan

Re: sequence manipulation functions

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

I wrote:

  > When the issue is to add a function to Emacs _as a documented
  > function_, something that is part of the name space users should not
  > know about and not interfere with, a name prefix is not necessary.

but I meant to write:

  > When the issue is to add a function to Emacs _as a documented
  > function_, something that is part of the name space users should
  > know about and not interfere with, a name prefix is not necessary.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.

Re: sequence manipulation functions

[Stefan Monnier]

> Here are two files that add some missing sequence-manipulation functions
> to Emacs Lisp.

I think these should use a "seq-" prefix.  This will not only avoid
naming conflicts, but also helps discover those functions, since you can
type `(seq- TAB' to see all related functions.

> ;;; Commentary:
>
> ;; Sequence manipulation functions

No need to repeat the title here.

> ;;;###autoload

It seems that pretty much all functions in this file are marked
as ;;;###autoload.  In that case I think it's better to not mark any of
them as autoloaded.

> (defun rest (seq)
>   "Return all but the first element of the sequence SEQ.
> If SEQ is nil or empty, return nil."

The different of cost between "rest of a list" and "rest of an array" is
so large that merging the two this way is probably not a good idea.

>   "Reduce two-argument FUNCTION across SEQ, starting with INITIAL-VALUE if not nil."
>   (let ((acc (or initial-value (if (empty-p seq)
>                                    (funcall function)

You start by saying "two-argument FUNCTION" and then you call it here
without any argument.

>     (mapc (lambda (item)
>             (setq acc (funcall function acc item)))
>           (if initial-value seq (rest seq)))

I don't think using `rest' here is a good idea when`seq' is an array.

>   "Sort the sequence SEQ comparing elements using PRED."

It needs to say that it returns a list rather than a sequence of the
same type as SEQ.


        Stefan

Re: sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

Thank you for your feedback.

>> Here are two files that add some missing sequence-manipulation functions
>> to Emacs Lisp.
>
> I think these should use a "seq-" prefix.  This will not only avoid
> naming conflicts, but also helps discover those functions, since you can
> type `(seq- TAB' to see all related functions.

I understand your point. Then what do you think about having all other
sequence functions prefixed with "seq-"? Maybe with the exception of
some really basic ones like "mapcar". For backward-compatibility, I
could keep the current names as aliases, and maybe later obsolete them.

>
>> ;;; Commentary:
>>
>> ;; Sequence manipulation functions
>
> No need to repeat the title here.
>
>> ;;;###autoload
>
> It seems that pretty much all functions in this file are marked
> as ;;;###autoload.  In that case I think it's better to not mark any of
> them as autoloaded.

Yes, you are right.

>
>> (defun rest (seq)
>>   "Return all but the first element of the sequence SEQ.
>> If SEQ is nil or empty, return nil."
>
> The different of cost between "rest of a list" and "rest of an array" is
> so large that merging the two this way is probably not a good idea.

Do you mean that the implementation is lacking in some way or that you
would remove the "rest" function all together?


Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Sebastien Vauban]

Nicolas Petton wrote:
>>> ;;;###autoload
>>
>> It seems that pretty much all functions in this file are marked
>> as ;;;###autoload.  In that case I think it's better to not mark any of
>> them as autoloaded.
>
> Yes, you are right.

Why?  Isn't it still useful for packages in general (and ELPA in
particular) so that autoloads files are generated, and these only are
what's needed to be loaded... allowing performance gains at startup?

Best regards,
  Seb

-- 
Sebastien Vauban

Re: sequence manipulation functions

[Stefan Monnier]

> I understand your point.  Then what do you think about having all other
> sequence functions prefixed with "seq-"?

Yes, you'll want to add seq-* aliases for things like elt.

> For backward-compatibility, I could keep the current names as aliases,
> and maybe later obsolete them.

We can start by having seq-elt be an alias for elt (rather than the
other way around) so as not to need changing anything else.

>> The different of cost between "rest of a list" and "rest of an array" is
>> so large that merging the two this way is probably not a good idea.
> Do you mean that the implementation is lacking in some way or that you
> would remove the "rest" function all together?

I think it's not just an implementation detail but a fundamental
limitation, so I'd just remove it.  Those who really want it can use
subseq (or whatever its new name will be, e.g. seq-subseq).

Sebastien Vauban <sva-news@mygooglest.com> writes:
> Why?  Isn't it still useful for packages in general (and ELPA in
> particular) so that autoloads files are generated, and these only are
> what's needed to be loaded... allowing performance gains at startup?

You might as well put a

   ;;;###autoload (require 'seq)

at that point (or add it to loadup.el).


        Stefan

[PATCH] sequence manipulation functions

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 95 bytes --]

Hi,

Here is a patch containing the new version of sequences.el and its
associated test file.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: sequences.diff --]
[-- Type: text/x-patch, Size: 11983 bytes --]

=== modified file 'lisp/ChangeLog'
--- lisp/ChangeLog	2014-11-07 10:49:22 +0000
+++ lisp/ChangeLog	2014-11-07 17:23:09 +0000
@@ -1,3 +1,7 @@
+2014-11-07  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* emacs-lisp/sequences.el: New file.
+
 2014-11-07  Martin Rudalics  <rudalics@gmx.at>
 
 	* cus-start.el (frame-resize-pixelwise): Fix group.

=== added file 'lisp/emacs-lisp/sequences.el'
--- lisp/emacs-lisp/sequences.el	1970-01-01 00:00:00 +0000
+++ lisp/emacs-lisp/sequences.el	2014-11-07 17:28:33 +0000
@@ -0,0 +1,137 @@
+;;; sequences.el --- Sequence manipulation functions  -*- lexical-binding: t -*-
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Keywords: sequences
+
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Sequence manipulation functions
+
+;;; Code:
+
+(require 'pcase)
+
+(defun seq-drop (n seq)
+  "Return a subsequence, without its first N elements, of the sequence SEQ."
+  (let ((length (seq-length seq)))
+    (seq-subseq seq (min n length) length)))
+
+(defun seq-take (n seq)
+  "Return a sequence of the first N elements of SEQ."
+  (seq-subseq seq 0 (min n (seq-length seq))))
+
+(defun seq-filter (pred seq)
+  "Return a list filtering with PRED all elements of SEQ."
+  (delq nil (mapcar (lambda (elt)
+                      (and (funcall pred elt) elt))
+                    seq)))
+
+(defun seq-reduce (function seq &optional initial-value)
+  "Reduce FUNCTION across SEQ, starting with INITIAL-VALUE if not nil."
+  (or (listp seq) (setq seq (append seq '())))
+  (let ((acc (or initial-value (if (seq-empty-p seq)
+                                   (funcall function)
+                                 (car seq)))))
+    (mapc (lambda (item)
+            (setq acc (funcall function acc item)))
+          (if initial-value seq (cdr seq)))
+    acc))
+
+(defun seq-some-p (pred seq)
+  "Return any element for which PRED is true in SEQ, nil otherwise."
+  (catch 'seq-some-p-break
+    (mapc (lambda (elt)
+            (when (funcall pred elt)
+              (throw 'seq-some-p-break elt)))
+          seq)
+    nil))
+
+(defun seq-every-p (pred seq)
+  "Return t if (PRED item) is non-nil for all elements of the sequence SEQ."
+  (catch 'seq-every-p-break
+    (mapc (lambda (elt)
+            (or (funcall pred elt)
+                (throw 'seq-every-p-break nil)))
+          seq)
+    t))
+
+(defun seq-empty-p (seq)
+  "Return t if the sequence SEQ is empty, nil otherwise."
+  (= 0 (seq-length seq)))
+
+(defun seq-sort (seq pred)
+  "Return a sorted list of the elements of SEQ compared using PRED."
+  (if (listp seq)
+      (sort (seq-copy seq) pred)
+    (seq-sort (append seq nil) pred)))
+
+(defun seq-contains-p (seq elt &optional testfn)
+  "Return the first element in SEQ that equals to ELT.
+Equality is defined by TESTFN if not nil or by `equal' if nil."
+  (seq-some-p (lambda (e)
+                (funcall (or testfn #'equal) elt e))
+              seq))
+
+(defun seq-uniq (seq &optional testfn)
+  "Return a list of the elements of SEQ with duplicates removed.
+Use TESTFN to compare elements, or `equal' if TESTFN is nil."
+  (let ((result '()))
+    (mapc (lambda (elt)
+            (unless (seq-contains-p result elt testfn)
+              (setq result (cons elt result))))
+          seq)
+    (nreverse result)))
+
+
+(defun seq-subseq (seq start &optional end)
+  "Return the subsequence of SEQ from START to END.
+If END is omitted, it defaults to the length of the sequence.
+If START or END is negative, it counts from the end."
+  (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
+        ((listp seq)
+         (let (len)
+           (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
+           (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
+           (if (> start 0) (setq seq (nthcdr start seq)))
+           (if end
+               (let ((res nil))
+                 (while (>= (setq end (1- end)) start)
+                   (push (pop seq) res))
+                 (nreverse res))
+             (seq-copy seq))))
+        (t (error "Unsupported sequence: %s" seq))))
+
+(defun seq-concatenate (type &rest seqs)
+  "Concatenate, into a sequence of type TYPE, the argument SEQS.
+\n(fn TYPE SEQUENCE...)"
+  (pcase type
+    (`vector (apply #'vconcat seqs))
+    (`string (apply #'concat seqs))
+    (`list (apply #'append (append seqs '(nil))))
+    (t (error "Not a sequence type name: %s" type))))
+
+(defalias 'seq-copy #'copy-sequence)
+(defalias 'seq-elt #'elt)
+(defalias 'seq-length #'length)
+
+(provide 'sequences)
+;;; sequences.el ends here

=== modified file 'lisp/loadup.el'
--- lisp/loadup.el	2014-10-15 17:32:41 +0000
+++ lisp/loadup.el	2014-11-07 17:17:48 +0000
@@ -93,6 +93,7 @@
 
 (load "version")
 
+(load "emacs-lisp/sequences")
 (load "widget")
 (load "custom")
 (load "emacs-lisp/map-ynp")

=== modified file 'test/ChangeLog'
--- test/ChangeLog	2014-10-28 20:33:12 +0000
+++ test/ChangeLog	2014-11-07 17:20:11 +0000
@@ -1,3 +1,7 @@
+2014-11-07  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* automated/sequences-tests.el: New file.
+
 2014-10-28  Ulf Jasper  <ulf.jasper@web.de>
 
 	* automated/libxml-tests.el: New file.

=== added file 'test/automated/sequences-tests.el'
--- test/automated/sequences-tests.el	1970-01-01 00:00:00 +0000
+++ test/automated/sequences-tests.el	2014-11-07 17:28:47 +0000
@@ -0,0 +1,153 @@
+;;; sequences-tests.el --- Tests for sequences.el
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Tests for sequences.el
+
+;;; Code:
+
+(require 'ert)
+(require 'sequences)
+
+(defmacro with-test-sequences (spec &rest body)
+  "Successively bind VAR to a list, vector, and string built from SEQ.
+Evaluate BODY for each created sequence.
+
+\(fn (var seq) body)"
+  (declare (indent 1) (debug ((symbolp form) body)))
+  (let ((initial-seq (make-symbol "initial-seq")))
+    `(let ((,initial-seq ,(cadr spec))) 
+       ,@(mapcar (lambda (s)
+                   `(let ((,(car spec) (apply (function ,s) ,initial-seq)))
+                      ,@body))
+                 '(list vector string)))))
+
+(defun same-contents-p (seq1 seq2)
+  "Return t if SEQ1 and SEQ2 have the same contents, nil otherwise."
+  (equal (append seq1 '()) (append seq2 '())))
+
+(ert-deftest test-seq-drop ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (equal (seq-drop 0 seq) seq))
+    (should (equal (seq-drop 1 seq) (seq-rest seq)))
+    (should (equal (seq-drop 2 seq) (seq-rest (seq-rest seq))))
+    (should (seq-empty-p (seq-drop 4 seq)))
+    (should (seq-empty-p (seq-drop 10 seq))))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p (seq-drop 0 seq)))
+    (should (seq-empty-p (seq-drop 1 seq)))))
+
+(ert-deftest test-seq-take ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (seq-empty-p (seq-take 0 seq)))
+    (should (= (seq-length (seq-take 1 seq)) 1))
+    (should (= (seq-first (seq-take 1 seq)) 2))
+    (should (same-contents-p (seq-take 3 seq) '(2 3 4)))
+    (should (equal (seq-take 10 seq) seq))))
+
+(ert-deftest test-seq-filter ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-filter #'evenp seq) '(6 8 10)))
+    (should (equal (seq-filter #'oddp seq) '(7 9)))
+    (should (equal (seq-filter (lambda (elt) nil) seq) '())))
+  (with-test-sequences (seq '())
+    (should (equal (seq-filter #'evenp seq) '()))))
+
+(ert-deftest test-seq-reduce ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (= (seq-reduce #'+ seq) 10))
+    (should (= (seq-reduce #'+ seq 5) 15)))
+  (with-test-sequences (seq '())
+    (should (eq (seq-reduce #'+ seq) 0))
+    (should (eq (seq-reduce #'+ seq 7) 7))))
+
+(ert-deftest test-seq-some-p ()
+  (with-test-sequences (seq '(4 3 2 1))
+    (should (= (seq-some-p #'evenp seq) 4))
+    (should (= (seq-some-p #'oddp seq) 3))
+    (should-not (seq-some-p (lambda (elt) (> elt 10)) seq)))
+  (with-test-sequences (seq '())
+    (should-not (seq-some-p #'oddp seq))))
+
+(ert-deftest test-seq-contains-p ()
+  (with-test-sequences (seq '(3 4 5 6))
+    (should (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq 7)))
+  (with-test-sequences (seq '())
+    (should-not (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq nil))))
+
+(ert-deftest test-seq-every-p ()
+  (with-test-sequences (seq '(43 54 22 1))
+    (should (seq-every-p (lambda (elt) t) seq))
+    (should-not (seq-every-p #'oddp seq))
+    (should-not (seq-every-p #'evenp seq)))
+  (with-test-sequences (seq '(42 54 22 2))
+    (should (seq-every-p #'evenp seq))
+    (should-not (seq-every-p #'oddp seq)))
+  (with-test-sequences (seq '())
+    (should (seq-every-p #'identity seq))
+    (should (seq-every-p #'evenp seq))))
+
+(ert-deftest test-seq-empty-p ()
+  (with-test-sequences (seq '(0))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '(0 1 2))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p seq))))
+
+(ert-deftest test-seq-sort ()
+  (with-test-sequences (seq '(89 32 12 3 5 1 1))
+    (should (equal (seq-sort seq #'<) '(1 1 3 5 12 32 89))))
+  (with-test-sequences (seq '())
+    (should (equal (seq-sort seq #'<) '()))))
+
+(ert-deftest test-seq-uniq ()
+  (with-test-sequences (seq '(2 4 6 8 6 4 3))
+    (should (equal (seq-uniq seq) '(2 4 6 8 3))))
+  (with-test-sequences (seq '(3 3 3 3 3))
+    (should (equal (seq-uniq seq) '(3))))
+  (with-test-sequences (seq '())
+    (should (equal (seq-uniq seq) '()))))
+
+(ert-deftest test-seq-subseq ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (equal (seq-subseq seq 0 4) seq))
+    (should (equal (seq-subseq seq 2 4) (seq-rest (seq-rest seq))))
+    (should (same-contents-p (seq-subseq seq 1 3) '(3 4)))
+    (should (same-contents-p (seq-subseq seq 1 -1) '(3 4))))
+  (should (vectorp (seq-subseq [2 3 4 5] 2)))
+  (should (stringp (seq-subseq "foo" 2 3)))
+  (should (listp (seq-subseq '(2 3 4 4) 2 3))))
+
+(ert-deftest test-seq-concatenate ()
+  (with-test-sequences (seq '(2 4 6))
+    (should (equal (seq-concatenate 'string seq [8]) (string 2 4 6 8)))
+    (should (equal (seq-concatenate 'list seq '(8 10)) '(2 4 6 8 10)))
+    (should (equal (seq-concatenate 'vector seq '(8 10)) [2 4 6 8 10]))
+    (should (equal (seq-concatenate 'vector nil '(8 10)) [8 10]))
+    (should (equal (seq-concatenate 'vector seq nil) [2 4 6]))))
+
+(provide 'sequences-tests)
+;;; sequences-tests.el ends here


[-- Attachment #3: Type: text/plain, Size: 1707 bytes --]


- I added the prefix "seq-" to all functions
- I removed "seq-first" and "seq-rest"
- I added "seq-contains-p" and "seq-uniq"
- Both new functions are tested
- I rewrote "seq-some-p"
- "sequences.el" is loaded in "loadup.el"

I'm also willing to document these functions in the Elisp manual.

Regards,
Nico


Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I understand your point.  Then what do you think about having all other
>> sequence functions prefixed with "seq-"?
>
> Yes, you'll want to add seq-* aliases for things like elt.
>
>> For backward-compatibility, I could keep the current names as aliases,
>> and maybe later obsolete them.
>
> We can start by having seq-elt be an alias for elt (rather than the
> other way around) so as not to need changing anything else.
>
>>> The different of cost between "rest of a list" and "rest of an array" is
>>> so large that merging the two this way is probably not a good idea.
>> Do you mean that the implementation is lacking in some way or that you
>> would remove the "rest" function all together?
>
> I think it's not just an implementation detail but a fundamental
> limitation, so I'd just remove it.  Those who really want it can use
> subseq (or whatever its new name will be, e.g. seq-subseq).
>
> Sebastien Vauban <sva-news@mygooglest.com> writes:
>> Why?  Isn't it still useful for packages in general (and ELPA in
>> particular) so that autoloads files are generated, and these only are
>> what's needed to be loaded... allowing performance gains at startup?
>
> You might as well put a
>
>    ;;;###autoload (require 'seq)
>
> at that point (or add it to loadup.el).
>
>
>         Stefan

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Daniel Colascione]

[-- Attachment #1: Type: text/plain, Size: 660 bytes --]


On 11/07/2014 05:35 PM, Nicolas Petton wrote:
> Hi,
> 
> Here is a patch containing the new version of sequences.el and its
> associated test file

Why do you want to dump these functions with Emacs?

> +(defun seq-sort (seq pred)
> +  "Return a sorted list of the elements of SEQ compared using PRED."
> +  (if (listp seq)
> +      (sort (seq-copy seq) pred)
> +    (seq-sort (append seq nil) pred)))

If you insist on adding seq- prefixed functions (and I don't think you
should, contra rms), you should make an alias, not a wrapper. You're
aware that we have native sort support for vectors and don't to coerce
to a list first, right?


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

> +;; Sequence manipulation functions

As noticed in the previous review, this just repeats what's already on
the first line, so that's not useful.  OTOH An important info would be
to define what we mean by "sequence" here, more specifically which kinds
of sequences are supported.

Also we could document here the conventions that we tried to follow.
E.g. what is the argument ordering.

> +(require 'pcase)

Why?  The `pcase' macro is autoloaded, so you should only need to
(require 'pcase) if you want top use macros like pcase-dolist.

> +(defun seq-filter (pred seq)
> +  "Return a list filtering with PRED all elements of SEQ."

Doesn't say if PRED returning nil means "keep" or "throw away".

> +  (delq nil (mapcar (lambda (elt)
> +                      (and (funcall pred elt) elt))
> +                    seq)))

This will filter out the nil elements, regardless of `pred'.

> +(defun seq-reduce (function seq &optional initial-value)
> +  "Reduce FUNCTION across SEQ, starting with INITIAL-VALUE if not nil."

You don't say how FUNCTION will be called.

> +  (or (listp seq) (setq seq (append seq '())))
> +  (let ((acc (or initial-value (if (seq-empty-p seq)
> +                                   (funcall function)
> +                                 (car seq)))))

If you want an initial value of nil but your function can only be called
with 2 arguments, you're screwed :-(
Would it be a real problem if we simply made `initial-value' an
mandatory argument?

> +(defun seq-some-p (pred seq)
> +  "Return any element for which PRED is true in SEQ, nil otherwise."
                                           ^^^^
Usually we say "non-nil".

> +  (catch 'seq-some-p-break

Since this tag is internal, I'd use a "seq--" prefix.  I think
`seq--break' should be sufficient.  Of course you could also just use
cl-block and cl-return and circumvent the question.

> +(defun seq-every-p (pred seq)
> +  "Return t if (PRED item) is non-nil for all elements of the sequence SEQ."
             ^
          non-nil

> +(defun seq-empty-p (seq)
> +  "Return t if the sequence SEQ is empty, nil otherwise."
             ^
          non-nil

> +(defun seq-sort (seq pred)
> +  "Return a sorted list of the elements of SEQ compared using PRED."

I wonder if that's really the more useful behavior, compared to the
"inplace" sorting of `sort', or compared to the alternative is always
returning a new sequence, but of the same type as the `seq' argument.

> +(defun seq-concatenate (type &rest seqs)
> +  "Concatenate, into a sequence of type TYPE, the argument SEQS.
> +\n(fn TYPE SEQUENCE...)"

You need to document the values that TYPE can take.  Maybe you can
simply refer to `type-of'.

> +(defalias 'seq-copy #'copy-sequence)
> +(defalias 'seq-elt #'elt)
> +(defalias 'seq-length #'length)

I think mapc would make a lot of sense, and I guess mapcar as well.
Not sure if we should name them `seq-mapc' and `seq-mapcar' or
something else.

> +(load "emacs-lisp/sequences")

I think I'd rather not preload it for now and let people use (require
'seq) for that.  There's 30 years of accumulated Elisp code and we're
not going to switch them to use a new naming scheme overnight.  It might
even be that people will simply not like to have to add "seq-" in their
code (I know they complained about adding "cl-"), so I'd start by simply
providing the library and when its popularity grows (and/or is being
used by preloaded code) we can then add it to loadup.


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Thank you Stefan for your review. I will submit another patch shortly.

Nico


Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> +;; Sequence manipulation functions
>
> As noticed in the previous review, this just repeats what's already on
> the first line, so that's not useful.  OTOH An important info would be
> to define what we mean by "sequence" here, more specifically which kinds
> of sequences are supported.
>
> Also we could document here the conventions that we tried to follow.
> E.g. what is the argument ordering.
>
>> +(require 'pcase)
>
> Why?  The `pcase' macro is autoloaded, so you should only need to
> (require 'pcase) if you want top use macros like pcase-dolist.
>
>> +(defun seq-filter (pred seq)
>> +  "Return a list filtering with PRED all elements of SEQ."
>
> Doesn't say if PRED returning nil means "keep" or "throw away".
>
>> +  (delq nil (mapcar (lambda (elt)
>> +                      (and (funcall pred elt) elt))
>> +                    seq)))
>
> This will filter out the nil elements, regardless of `pred'.
>
>> +(defun seq-reduce (function seq &optional initial-value)
>> +  "Reduce FUNCTION across SEQ, starting with INITIAL-VALUE if not nil."
>
> You don't say how FUNCTION will be called.
>
>> +  (or (listp seq) (setq seq (append seq '())))
>> +  (let ((acc (or initial-value (if (seq-empty-p seq)
>> +                                   (funcall function)
>> +                                 (car seq)))))
>
> If you want an initial value of nil but your function can only be called
> with 2 arguments, you're screwed :-(
> Would it be a real problem if we simply made `initial-value' an
> mandatory argument?
>
>> +(defun seq-some-p (pred seq)
>> +  "Return any element for which PRED is true in SEQ, nil otherwise."
>                                            ^^^^
> Usually we say "non-nil".
>
>> +  (catch 'seq-some-p-break
>
> Since this tag is internal, I'd use a "seq--" prefix.  I think
> `seq--break' should be sufficient.  Of course you could also just use
> cl-block and cl-return and circumvent the question.
>
>> +(defun seq-every-p (pred seq)
>> +  "Return t if (PRED item) is non-nil for all elements of the sequence SEQ."
>              ^
>           non-nil
>
>> +(defun seq-empty-p (seq)
>> +  "Return t if the sequence SEQ is empty, nil otherwise."
>              ^
>           non-nil
>
>> +(defun seq-sort (seq pred)
>> +  "Return a sorted list of the elements of SEQ compared using PRED."
>
> I wonder if that's really the more useful behavior, compared to the
> "inplace" sorting of `sort', or compared to the alternative is always
> returning a new sequence, but of the same type as the `seq' argument.
>
>> +(defun seq-concatenate (type &rest seqs)
>> +  "Concatenate, into a sequence of type TYPE, the argument SEQS.
>> +\n(fn TYPE SEQUENCE...)"
>
> You need to document the values that TYPE can take.  Maybe you can
> simply refer to `type-of'.
>
>> +(defalias 'seq-copy #'copy-sequence)
>> +(defalias 'seq-elt #'elt)
>> +(defalias 'seq-length #'length)
>
> I think mapc would make a lot of sense, and I guess mapcar as well.
> Not sure if we should name them `seq-mapc' and `seq-mapcar' or
> something else.
>
>> +(load "emacs-lisp/sequences")
>
> I think I'd rather not preload it for now and let people use (require
> 'seq) for that.  There's 30 years of accumulated Elisp code and we're
> not going to switch them to use a new naming scheme overnight.  It might
> even be that people will simply not like to have to add "seq-" in their
> code (I know they complained about adding "cl-"), so I'd start by simply
> providing the library and when its popularity grows (and/or is being
> used by preloaded code) we can then add it to loadup.
>
>
>         Stefan

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>> +  (or (listp seq) (setq seq (append seq '())))
>> +  (let ((acc (or initial-value (if (seq-empty-p seq)
>> +                                   (funcall function)
>> +                                 (car seq)))))
>
> If you want an initial value of nil but your function can only be called
> with 2 arguments, you're screwed :-(
> Would it be a real problem if we simply made `initial-value' an
> mandatory argument?

No, I think that's fine.

>> +  (catch 'seq-some-p-break
>
> Since this tag is internal, I'd use a "seq--" prefix.  I think
> `seq--break' should be sufficient.  Of course you could also just use
> cl-block and cl-return and circumvent the question.

Sure, I will use seq--break.

>> +(defun seq-sort (seq pred)
>> +  "Return a sorted list of the elements of SEQ compared using PRED."
>
> I wonder if that's really the more useful behavior, compared to the
> "inplace" sorting of `sort', or compared to the alternative is always
> returning a new sequence, but of the same type as the `seq' argument.

I can make it return a sequence of the same type as seq. I don't want to
sort in place though, all other functions leave seq untouched, and I
would like to keep it this way.

>> +(defalias 'seq-copy #'copy-sequence)
>> +(defalias 'seq-elt #'elt)
>> +(defalias 'seq-length #'length)
>
> I think mapc would make a lot of sense, and I guess mapcar as well.
> Not sure if we should name them `seq-mapc' and `seq-mapcar' or
> something else.

How do "seq-do" and "seq-map" sound like?

I'm not confortable with "seq-doseq" or something like that since I
would expect it to be a macro similar to "dolist".

>
>> +(load "emacs-lisp/sequences")
>
> I think I'd rather not preload it for now and let people use (require
> 'seq) for that.  There's 30 years of accumulated Elisp code and we're
> not going to switch them to use a new naming scheme overnight.  It might
> even be that people will simply not like to have to add "seq-" in their
> code (I know they complained about adding "cl-"), so I'd start by simply
> providing the library and when its popularity grows (and/or is being
> used by preloaded code) we can then add it to loadup.

Fair enough. One question though, if sequences.el is not preloaded, then
I guess these functions should not be documented in the manual? But
then, how will people find out about it? If nobody knows about it, then
it makes it much less likely to be used :)

Nico

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

>> I wonder if that's really the more useful behavior, compared to the
>> "inplace" sorting of `sort', or compared to the alternative is always
>> returning a new sequence, but of the same type as the `seq' argument.
> I can make it return a sequence of the same type as seq.

I was really just asking.  But at least it seems that returning the same
type will save people from having to convert the list back to an array
if that's what they were after.

> I don't want to sort in place though, all other functions leave seq
> untouched, and I would like to keep it this way.

I don't like side-effects much myself, so I'm fine with that.

> How do "seq-do" and "seq-map" sound like?

Good.

> I'm not confortable with "seq-doseq" or something like that since I
> would expect it to be a macro similar to "dolist".

A dolist-style macro would also be welcome.  If it could even avoid
calling a function at each iteration, it would be even better.

> Fair enough. One question though, if sequences.el is not preloaded, then
> I guess these functions should not be documented in the manual?

Why not?  Just state that they need a (require 'seq) before you can use them.


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Fair enough. One question though, if sequences.el is not preloaded, then
>> I guess these functions should not be documented in the manual?
>
> Why not?  Just state that they need a (require 'seq) before you can
> use them.

Should I put it in the Elisp manual in sequences.texi?

Nicolas

Re: [PATCH] sequence manipulation functions

[Bozhidar Batsov]

[-- Attachment #1: Type: text/plain, Size: 1244 bytes --]

I don’t see here common sequence functions like take-while, drop-while, remove (the opposite of filter), mapcat, flatten, etc. 
The clojure standard library and dash.el can be used as reference for adding other useful functions as well. Such a library should eliminate the need for third-party libs like `dash.el`. I find it amusing that there were suggestions about a similar library last year and they were quickly shot down…

Anyways, for the prefixing to make sense functions like mapcar,  mapc and friends should be aliased as well (ideally with names like `seq-map`, `sea-each`, etc).  

Another thing to consider - if you want the library to be adopted quickly it might make sense to distribute it as a ELPA package for older Emacsen.

— 
Cheers,
Bozhidar

On November 12, 2014 at 19:50:16, Nicolas Petton (petton.nicolas@gmail.com) wrote:


Stefan Monnier <monnier@iro.umontreal.ca> writes:  

>> Fair enough. One question though, if sequences.el is not preloaded, then  
>> I guess these functions should not be documented in the manual?  
>  
> Why not? Just state that they need a (require 'seq) before you can  
> use them.  

Should I put it in the Elisp manual in sequences.texi?  

Nicolas  


[-- Attachment #2: Type: text/html, Size: 2873 bytes --]

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Bozhidar Batsov <bozhidar.batsov@gmail.com> writes:

> I don’t see here common sequence functions like take-while,
> drop-while, remove (the opposite of filter), mapcat, flatten, etc.

There are indeed missing functions. As I initially planned to add these
functions without any prefix and propose the change in subr.el, I didn't
want to add too many of them at once, but now I can definitely add the
missing ones.

seq-take and seq-drop were rejected though, so I don't think take-while
or drop-while make much sense anymore. Or?

> Anyways, for the prefixing to make sense functions like mapcar, mapc
> and friends should be aliased as well (ideally with names like
> `seq-map`, `sea-each`, etc). 

Yes, I did alias them. I aliased mapc to seq-do though.

>
> Another thing to consider - if you want the library to be adopted
> quickly it might make sense to distribute it as a ELPA package for
> older Emacsen.

That's a very good point!

Nico

>
> —
> Cheers,
> Bozhidar
>
> On November 12, 2014 at 19:50:16, Nicolas Petton (petton.nicolas@gmail.com) wrote:
>
>
> Stefan Monnier <monnier@iro.umontreal.ca> writes:  
>
>>> Fair enough. One question though, if sequences.el is not preloaded, then  
>>> I guess these functions should not be documented in the manual?  
>>  
>> Why not? Just state that they need a (require 'seq) before you can  
>> use them.  
>
> Should I put it in the Elisp manual in sequences.texi?  
>
> Nicolas  

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

> seq-take and seq-drop were rejected though,

When?


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> seq-take and seq-drop were rejected though,

Sorry, forget what I said, it was seq-first and seq-rest.

Nico

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 92 bytes --]

Hi,

Here is a new version of the patch that I hope addresses all of your
comments Stefan.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: seq.diff --]
[-- Type: text/x-patch, Size: 15712 bytes --]

=== modified file 'lisp/ChangeLog'
--- lisp/ChangeLog	2014-11-07 10:49:22 +0000
+++ lisp/ChangeLog	2014-11-12 22:50:37 +0000
@@ -1,3 +1,7 @@
+2014-11-12  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* emacs-lisp/seq.el: New file.
+
 2014-11-07  Martin Rudalics  <rudalics@gmx.at>
 
 	* cus-start.el (frame-resize-pixelwise): Fix group.

=== added file 'lisp/emacs-lisp/seq.el'
--- lisp/emacs-lisp/seq.el	1970-01-01 00:00:00 +0000
+++ lisp/emacs-lisp/seq.el	2014-11-12 22:51:45 +0000
@@ -0,0 +1,212 @@
+;;; seq.el --- Sequence manipulation functions  -*- lexical-binding: t -*-
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Keywords: sequences
+
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Sequence-manipulation functions that complement basic functions
+;; provided by subr.el.
+;;
+;; All functions are prefixed with "seq-".
+;;
+;; All provided functions work on lists, strings and vectors.
+;;
+;; Functions taking a predicate or a function iterating over the
+;; sequence as argument take the function as their first argument and
+;; the sequence as their second argument.  All other functions take
+;; the sequence as their first argument.
+;;
+;; All functions are tested in test/automated/seq-tests.el
+
+;;; Code:
+
+(defun seq-drop (seq n)
+  "Return a subsequence of SEQ without its first N elements.
+The result is a sequence of the same type as SEQ."
+  (let ((length (seq-length seq)))
+    (seq-subseq seq (min n length) length)))
+
+(defun seq-take (seq n)
+  "Return a subsequence of SEQ with its first N elements.
+The result is a sequence of the same type as SEQ."
+  (seq-subseq seq 0 (min n (seq-length seq))))
+
+(defun seq-drop-while (pred seq)
+  "Return a subsequence, from the first element for which (PRED element) is nil, of SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-drop seq n)))
+
+(defun seq-take-while (pred seq)
+  "Return a subsequence of the successive elements for which (PRED element) is non-nil in SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-take seq n)))
+
+(defun seq-filter (pred seq)
+  "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
+  (delq 'seq--exclude (seq-map (lambda (elt)
+                                (if (funcall pred elt)
+                                    elt
+                                  'seq--exclude))
+                              seq)))
+
+(defun seq-remove (pred seq)
+  "Return a list of all the elements for which (PRED element) is nil in SEQ."
+  (seq-filter (lambda (elt) (not (funcall pred elt)))
+              seq))
+
+(defun seq-reduce (function seq initial-value)
+  "Reduce the two-arguments function FUNCTION across SEQ, starting with INITIAL-VALUE.
+
+Return the result of applying FUNCTION to INITIAL-VALUE and the
+first element of SEQ, then applying FUNCTION to that result and
+the second element of SEQ, then to that result and the third
+element of SEQ, etc.
+
+If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
+  (if (seq-empty-p seq)
+      initial-value
+    (let ((acc initial-value))
+      (seq-doseq (elt seq)
+        (setq acc (funcall function acc elt)))
+      acc)))
+
+(defun seq-some-p (pred seq)
+  "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (throw 'seq--break elt)))
+    nil))
+
+(defun seq-every-p (pred seq)
+  "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (or (funcall pred elt)
+          (throw 'seq--break nil)))
+    t))
+
+(defun seq-count (pred seq)
+  "Return the number of elements for which (PRED element) in non-nil in seq."
+  (let ((count 0))
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (setq count (+ 1 count))))
+    count))
+
+(defun seq-empty-p (seq)
+  "Return non-nil if the sequence SEQ is empty, nil otherwise."
+  (= 0 (seq-length seq)))
+
+(defun seq-sort (pred seq)
+  "Return a sorted sequence comparing using PRED the elements of SEQ.
+The result is a sequence of the same type as SEQ."
+  (if (listp seq)
+      (sort (seq-copy seq) pred)
+    (let ((result (seq-sort pred (append seq nil))))
+      (cond ((stringp seq) (concat result))
+            ((vectorp seq) (vconcat result))
+            (t (error "Unsupported sequence: %s" seq))))))
+
+(defun seq-contains-p (seq elt &optional testfn)
+  "Return the first element in SEQ that equals to ELT.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+  (seq-some-p (lambda (e)
+                (funcall (or testfn #'equal) elt e))
+              seq))
+
+(defun seq-uniq (seq &optional testfn)
+  "Return a list of the elements of SEQ with duplicates removed.
+Use TESTFN to compare elements, or `equal' if TESTFN is nil."
+  (let ((result '()))
+    (seq-doseq (elt seq)
+      (unless (seq-contains-p result elt testfn)
+        (setq result (cons elt result))))
+    (nreverse result)))
+
+(defun seq-subseq (seq start &optional end)
+  "Return the subsequence of SEQ from START to END.
+If END is omitted, it defaults to the length of the sequence.
+If START or END is negative, it counts from the end."
+  (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
+        ((listp seq)
+         (let (len)
+           (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
+           (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
+           (if (> start 0) (setq seq (nthcdr start seq)))
+           (if end
+               (let ((res nil))
+                 (while (>= (setq end (1- end)) start)
+                   (push (pop seq) res))
+                 (nreverse res))
+             (seq-copy seq))))
+        (t (error "Unsupported sequence: %s" seq))))
+
+(defun seq-concatenate (type &rest seqs)
+  "Concatenate, into a sequence of type TYPE, the sequences SEQS.
+TYPE must be one of following symbols: vector, string or list.
+
+\n(fn TYPE SEQUENCE...)"
+  (pcase type
+    (`vector (apply #'vconcat seqs))
+    (`string (apply #'concat seqs))
+    (`list (apply #'append (append seqs '(nil))))
+    (t (error "Not a sequence type name: %s" type))))
+
+(defmacro seq-doseq (spec &rest body)
+  "Loop over a sequence.
+Similar to `dolist' but can be applied lists, strings and vectors.
+
+Evaluate BODY with VAR bound to each element of SEQ, in turn.
+Then evaluate RESULT to get return value, default nil.
+
+\(fn (VAR SEQ [RESULT]) BODY...)"
+  (declare (indent 1) (debug ((symbolp form &optional form) body)))
+  (let ((index (make-symbol "index"))
+        (seq (make-symbol "seq")))
+    `(let ((,index 0)
+           (,seq ,(cadr spec)))
+       (while (< ,index (seq-length ,seq))
+         (let ((,(car spec) (seq-elt ,seq ,index)))
+           ,@body
+           (setq ,index (+ ,index 1))))
+       ,@(if (cddr spec)
+             `((setq ,(car spec) nil) ,@(cddr spec))))))
+
+(defalias 'seq-copy #'copy-sequence)
+(defalias 'seq-elt #'elt)
+(defalias 'seq-length #'length)
+(defalias 'seq-do #'mapc)
+(defalias 'seq-each #'seq-do)
+(defalias 'seq-map #'mapcar)
+
+(provide 'seq)
+;;; seq.el ends here

=== modified file 'test/ChangeLog'
--- test/ChangeLog	2014-10-28 20:33:12 +0000
+++ test/ChangeLog	2014-11-12 22:50:48 +0000
@@ -1,3 +1,7 @@
+2014-11-12  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* automated/seq-tests.el: New file.
+
 2014-10-28  Ulf Jasper  <ulf.jasper@web.de>
 
 	* automated/libxml-tests.el: New file.

=== added file 'test/automated/seq-tests.el'
--- test/automated/seq-tests.el	1970-01-01 00:00:00 +0000
+++ test/automated/seq-tests.el	2014-11-12 22:18:45 +0000
@@ -0,0 +1,177 @@
+;;; seq-tests.el --- Tests for sequences.el
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Tests for sequences.el
+
+;;; Code:
+
+(require 'ert)
+(require 'seq)
+
+(defmacro with-test-sequences (spec &rest body)
+  "Successively bind VAR to a list, vector, and string built from SEQ.
+Evaluate BODY for each created sequence.
+
+\(fn (var seq) body)"
+  (declare (indent 1) (debug ((symbolp form) body)))
+  (let ((initial-seq (make-symbol "initial-seq")))
+    `(let ((,initial-seq ,(cadr spec)))
+       ,@(mapcar (lambda (s)
+                   `(let ((,(car spec) (apply (function ,s) ,initial-seq)))
+                      ,@body))
+                 '(list vector string)))))
+
+(defun same-contents-p (seq1 seq2)
+  "Return t if SEQ1 and SEQ2 have the same contents, nil otherwise."
+  (equal (append seq1 '()) (append seq2 '())))
+
+(defun test-sequences-evenp (integer)
+  "Return t if INTEGER is even."
+  (eq (logand integer 1) 0))
+
+(defun test-sequences-oddp (integer)
+  "Return t if INTEGER is odd."
+  (not (test-sequences-evenp integer)))
+
+(ert-deftest test-seq-drop ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (equal (seq-drop seq 0) seq))
+    (should (equal (seq-drop seq 1) (seq-subseq seq 1)))
+    (should (equal (seq-drop seq 2) (seq-subseq seq 2)))
+    (should (seq-empty-p (seq-drop seq 4)))
+    (should (seq-empty-p (seq-drop seq 10))))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p (seq-drop seq 0)))
+    (should (seq-empty-p (seq-drop seq 1)))))
+
+(ert-deftest test-seq-take ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (seq-empty-p (seq-take seq 0)))
+    (should (= (seq-length (seq-take seq 1)) 1))
+    (should (= (seq-elt (seq-take seq 1) 0) 2))
+    (should (same-contents-p (seq-take seq 3) '(2 3 4)))
+    (should (equal (seq-take seq 10) seq))))
+
+(ert-deftest test-seq-filter ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-filter #'test-sequences-evenp seq) '(6 8 10)))
+    (should (equal (seq-filter #'test-sequences-oddp seq) '(7 9)))
+    (should (equal (seq-filter (lambda (elt) nil) seq) '())))
+  (with-test-sequences (seq '())
+    (should (equal (seq-filter #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-remove ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-remove #'test-sequences-evenp seq) '(7 9)))
+    (should (equal (seq-remove #'test-sequences-oddp seq) '(6 8 10)))
+    (should (same-contents-p (seq-remove (lambda (elt) nil) seq) seq)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-remove #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-count ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-count #'test-sequences-evenp seq) 3))
+    (should (equal (seq-count #'test-sequences-oddp seq) 2))
+    (should (equal (seq-count (lambda (elt) nil) seq) 0)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-count #'test-sequences-evenp seq) 0))))
+
+(ert-deftest test-seq-reduce ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (= (seq-reduce #'+ seq 0) 10))
+    (should (= (seq-reduce #'+ seq 5) 15)))
+  (with-test-sequences (seq '())
+    (should (eq (seq-reduce #'+ seq 0) 0))
+    (should (eq (seq-reduce #'+ seq 7) 7))))
+
+(ert-deftest test-seq-some-p ()
+  (with-test-sequences (seq '(4 3 2 1))
+    (should (= (seq-some-p #'test-sequences-evenp seq) 4))
+    (should (= (seq-some-p #'test-sequences-oddp seq) 3))
+    (should-not (seq-some-p (lambda (elt) (> elt 10)) seq)))
+  (with-test-sequences (seq '())
+    (should-not (seq-some-p #'test-sequences-oddp seq))))
+
+(ert-deftest test-seq-contains-p ()
+  (with-test-sequences (seq '(3 4 5 6))
+    (should (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq 7)))
+  (with-test-sequences (seq '())
+    (should-not (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq nil))))
+
+(ert-deftest test-seq-every-p ()
+  (with-test-sequences (seq '(43 54 22 1))
+    (should (seq-every-p (lambda (elt) t) seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq))
+    (should-not (seq-every-p #'test-sequences-evenp seq)))
+  (with-test-sequences (seq '(42 54 22 2))
+    (should (seq-every-p #'test-sequences-evenp seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq)))
+  (with-test-sequences (seq '())
+    (should (seq-every-p #'identity seq))
+    (should (seq-every-p #'test-sequences-evenp seq))))
+
+(ert-deftest test-seq-empty-p ()
+  (with-test-sequences (seq '(0))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '(0 1 2))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p seq))))
+
+(ert-deftest test-seq-sort ()
+  (should (equal (seq-sort #'< "cbaf") "abcf"))
+  (should (equal (seq-sort #'< '(2 1 9 4)) '(1 2 4 9)))
+  (should (equal (seq-sort #'< [2 1 9 4]) [1 2 4 9]))
+  (should (equal (seq-sort #'< "") "")))
+
+(ert-deftest test-seq-uniq ()
+  (with-test-sequences (seq '(2 4 6 8 6 4 3))
+    (should (equal (seq-uniq seq) '(2 4 6 8 3))))
+  (with-test-sequences (seq '(3 3 3 3 3))
+    (should (equal (seq-uniq seq) '(3))))
+  (with-test-sequences (seq '())
+    (should (equal (seq-uniq seq) '()))))
+
+(ert-deftest test-seq-subseq ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (equal (seq-subseq seq 0 4) seq))
+    (should (same-contents-p (seq-subseq seq 2 4) '(4 5)))
+    (should (same-contents-p (seq-subseq seq 1 3) '(3 4)))
+    (should (same-contents-p (seq-subseq seq 1 -1) '(3 4))))
+  (should (vectorp (seq-subseq [2 3 4 5] 2)))
+  (should (stringp (seq-subseq "foo" 2 3)))
+  (should (listp (seq-subseq '(2 3 4 4) 2 3))))
+
+(ert-deftest test-seq-concatenate ()
+  (with-test-sequences (seq '(2 4 6))
+    (should (equal (seq-concatenate 'string seq [8]) (string 2 4 6 8)))
+    (should (equal (seq-concatenate 'list seq '(8 10)) '(2 4 6 8 10)))
+    (should (equal (seq-concatenate 'vector seq '(8 10)) [2 4 6 8 10]))
+    (should (equal (seq-concatenate 'vector nil '(8 10)) [8 10]))
+    (should (equal (seq-concatenate 'vector seq nil) [2 4 6]))))
+
+(provide 'seq-tests)
+;;; seq-tests.el ends here


[-- Attachment #3: Type: text/plain, Size: 520 bytes --]


I have renamed the library "seq" instead of "sequences".

This patch also adds the following functions: seq-take-while,
seq-drop-while, seq-remove, seq-count, seq-do (as an alias to mapc),
seq-each (same alias), seq-map (as an alias to mapcar), as well as the
seq-doseq macro, similar to dolist.

If you think that some important functions are missing, please tell me.

I didn't add documentation yet, as I don't really know if it should be
in the Sequences section of the Elisp manual or somewhere else.

Cheers,
Nico

Re: [PATCH] sequence manipulation functions

[Nic Ferrier]

petton.nicolas@gmail.com writes:

> Here is a new version of the patch that I hope addresses all of your
> comments Stefan.

I think it's incredible that this is being considered.

Surely a better option is to put it into elpa.git and recommend it's use
for at least a release? rather than just putting it directly into emacs?

I don't understand why that is a good model at all.

This to me is like the whole "let's change the way cl works" thing that
Stefan did.


Nic

Re: [PATCH] sequence manipulation functions

[Leo Liu]

On 2014-11-12 23:17 +0000, Nic Ferrier wrote:
> I think it's incredible that this is being considered.
>
> Surely a better option is to put it into elpa.git and recommend it's use
> for at least a release? rather than just putting it directly into emacs?
>
> I don't understand why that is a good model at all.

Indeed this also confused me greatly. Folks, what are we doing here?

If we were to model another set of list/seq routines after other
functional languages, we need an undertaker that is willing to provide a
more complete initial version and hopefully introduce a few new features
to make it more appealing. It should probably base off some language
such as clojure/haskell but also review similar libraries in other
languages with elisp in mind. i.e. someone who is set out to provide a
>80% solution with consistency and the community in mind.

The author of cl/cl-lib did a great job to make it a 95% solution. Yes
it has ugliness here and there but it is unavoidable to a 95% solution
within the constraint of elisp/emacs. I think if his goal were to
provide a set of cl-like functions he would have succeeded more than
competently 2 decades ago.

Leo

RE: [PATCH] sequence manipulation functions

[Drew Adams]

> It should probably base off some language such as clojure/haskell

It should be based on the existing sequence functions in Common Lisp,
as stated earlier.  Such things were worked out for Lisp eons ago.
There is really no reason to do something very different, other
things being equal.

Re: [PATCH] sequence manipulation functions

[Leo Liu]

On 2014-11-13 13:21 +0800, Drew Adams wrote:
> It should be based on the existing sequence functions in Common Lisp,
> as stated earlier.  Such things were worked out for Lisp eons ago.
> There is really no reason to do something very different, other
> things being equal.

I think most people will like this option. So I was hypothesising what
was being done i.e. `If we were to model another set of list/seq
routines after other......' since we already have one after CL.

Leo

Re: [PATCH] sequence manipulation functions

[Bozhidar Batsov]

[-- Attachment #1: Type: text/plain, Size: 1607 bytes --]

There are relatively few sequence functions from CL in the standard library. The majority of them
reside in `cl-lib`, which IMO can’t be counted as part of the standard library. After all its own description
is:

;; These are extensions to Emacs Lisp that provide a degree of
;; Common Lisp compatibility, beyond what is already built-in
;; in Emacs Lisp.


While I’d prefer it we adopted the names from Scheme and Clojure (e.g. filter vs remove-if-not), I’m fine with leaning more in the CL
direction as long as this is done by promoting some cl-lib functions to the standard Emacs library. People shouldn’t have to require the entire `cl-lib` just for the same of a handful of sequence functions.

I don’t think it’s normal that pretty much every Emacs package depends on their `cl-lib` or the third party lib `dash.el`.
Emacs hackers obviously feel that the standard library is lacking and it should be improved somehow (preferably now instead
of next decade).

—
Cheers, 
Bozhidar

On November 14, 2014 at 7:16:49 AM, Leo Liu (sdl.web@gmail.com) wrote:

On 2014-11-13 13:21 +0800, Drew Adams wrote:  
> It should be based on the existing sequence functions in Common Lisp,  
> as stated earlier. Such things were worked out for Lisp eons ago.  
> There is really no reason to do something very different, other  
> things being equal.  

I think most people will like this option. So I was hypothesising what  
was being done i.e. `If we were to model another set of list/seq  
routines after other......' since we already have one after CL.  

Leo  



[-- Attachment #2: Type: text/html, Size: 4664 bytes --]

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Bozhidar Batsov <bozhidar.batsov@gmail.com> writes:

> There are relatively few sequence functions from CL in the standard library. The majority of them
> reside in `cl-lib`, which IMO can’t be counted as part of the standard library. After all its own description
> is:
>
> ;; These are extensions to Emacs Lisp that provide a degree of
> ;; Common Lisp compatibility, beyond what is already built-in
> ;; in Emacs Lisp.
>
>
> While I’d prefer it we adopted the names from Scheme and Clojure (e.g. filter vs remove-if-not), I’m fine with leaning more in the CL
> direction as long as this is done by promoting some cl-lib functions to the standard Emacs library. People shouldn’t have to require the entire `cl-lib` just for the same of a handful of sequence functions.
>
> I don’t think it’s normal that pretty much every Emacs package depends on their `cl-lib` or the third party lib `dash.el`.
> Emacs hackers obviously feel that the standard library is lacking and it should be improved somehow (preferably now instead
> of next decade).

I agree. Promoting some sequence-related cl-lib functions would also be
perfectly fine with me. I have no problem with adopting CL names, but I
do feel that the current standard library is lacking.

Cheers,
Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

RE: [PATCH] sequence manipulation functions

[Drew Adams]

> > I’m fine with leaning more in the CL direction as long as this
> > is done by promoting some cl-lib functions to the standard
> > Emacs library. People shouldn’t have to require the entire
> > `cl-lib` just for the same of a handful of sequence functions.
> >
> > I don’t think it’s normal that pretty much every Emacs package
> > depends on their `cl-lib` or the third party lib `dash.el`.
> > Emacs hackers obviously feel that the standard library is
> > lacking and it should be improved somehow (preferably now
> > instead of next decade).
> 
> I agree. Promoting some sequence-related cl-lib functions would
> also be perfectly fine with me. I have no problem with adopting
> CL names, but I do feel that the current standard library is
> lacking.

I am generally in favor of moving Emacs Lisp closer to Common
Lisp.  So I too think that this would be a good change.

That said, I don't mind having to use `require' or having such
things be autoloaded.  Perhaps further factoring of the CL Elisp
files would mean that less code would need to be loaded to use
such functions (dunno).  As BB said:

> > People shouldn’t have to require the entire `cl-lib` just
> > for the same of a handful of sequence functions.

I think that one of the reasons that I wouldn't have suggested
including such functions in Emacs Lisp in the past was that it
did not really support lexical binding.  And dynamic binding
makes extensive use of higher-order functions problematic.
But we have lexical binding now (thanks mainly to Stefan), so
that particular caveat is no longer applicable.

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

> I agree.  Promoting some sequence-related cl-lib functions would also be
> perfectly fine with me.  I have no problem with adopting CL names, but I
> do feel that the current standard library is lacking.

FWIW, I think it's perfectly OK for Elisp packages to start with
a list of `require's.

But w.r.t CL's sequence manipulation functions, the problem is that
there is no structure there, so it's hard to find the functions
you need if you don't already know their name.

A lot of Elisp's "standard library" shares this fundamental problem.
The "prefix convention" is not useful only as a way to avoid name
collisions (which would imply that it can be "ignored" for "core
functions") but is also a way to structure the library, and so far the
core functions have not being doing a very good job of it.


        Stefan

Re: [PATCH] sequence manipulation functions

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > FWIW, I think it's perfectly OK for Elisp packages to start with
  > a list of `require's.

For one package to load others is normal.  The problem with CL is
special because its functions don't have a name prefix.
-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I agree.  Promoting some sequence-related cl-lib functions would also be
>> perfectly fine with me.  I have no problem with adopting CL names, but I
>> do feel that the current standard library is lacking.
>
> FWIW, I think it's perfectly OK for Elisp packages to start with
> a list of `require's.

Sure, I agree.

>
> But w.r.t CL's sequence manipulation functions, the problem is that
> there is no structure there, so it's hard to find the functions
> you need if you don't already know their name.

Good point.

>
> A lot of Elisp's "standard library" shares this fundamental problem.
> The "prefix convention" is not useful only as a way to avoid name
> collisions (which would imply that it can be "ignored" for "core
> functions") but is also a way to structure the library, and so far the
> core functions have not being doing a very good job of it.

So, should I keep working on it? I was planning to start working on the
documentation. Would the Sequences section of the Elisp manual be the
right place?

Cheers,
Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

>> A lot of Elisp's "standard library" shares this fundamental problem.
>> The "prefix convention" is not useful only as a way to avoid name
>> collisions (which would imply that it can be "ignored" for "core
>> functions") but is also a way to structure the library, and so far the
>> core functions have not being doing a very good job of it.
> So, should I keep working on it?  I was planning to start working on the
> documentation.  Would the Sequences section of the Elisp manual be the
> right place?

Sounds good, yes.


        Stefan

Re: [PATCH] sequence manipulation functions

[Damien Cassou]

[-- Attachment #1: Type: text/plain, Size: 759 bytes --]

What are the news about this?
On Nov 13, 2014 12:06 AM, "Nicolas Petton" <petton.nicolas@gmail.com> wrote:

> Hi,
>
> Here is a new version of the patch that I hope addresses all of your
> comments Stefan.
>
>
>
> I have renamed the library "seq" instead of "sequences".
>
> This patch also adds the following functions: seq-take-while,
> seq-drop-while, seq-remove, seq-count, seq-do (as an alias to mapc),
> seq-each (same alias), seq-map (as an alias to mapcar), as well as the
> seq-doseq macro, similar to dolist.
>
> If you think that some important functions are missing, please tell me.
>
> I didn't add documentation yet, as I don't really know if it should be
> in the Sequences section of the Elisp manual or somewhere else.
>
> Cheers,
> Nico
>
>

[-- Attachment #2: Type: text/html, Size: 1096 bytes --]

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

> +(defun seq-filter (pred seq)
> +  "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
> +  (delq 'seq--exclude (seq-map (lambda (elt)
> +                                (if (funcall pred elt)
> +                                    elt
> +                                  'seq--exclude))
> +                              seq)))

This won't do the right thing if the list includes the symbol
`seq--exclude' (which could happen if this function is used by, say,
completion code).  Better do a (defvar seq--exclude (make-symbol "exclude"))
and then use the value of `seq--exclude' rather than the constant
`seq--exclude'.

> +  "Reduce the two-arguments function FUNCTION across SEQ, starting with INITIAL-VALUE.

This first line is too long.  I guess we need to drop the "two-arguments" part.

> I have renamed the library "seq" instead of "sequences".

Good.

> seq-doseq macro, similar to dolist.

Actually seq-doseq is "unusable" on lists: it's O(N^2) instead
of O(N).

Otherwise, it looks fine, thank you,


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>> +(defun seq-filter (pred seq)
>> +  "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
>> +  (delq 'seq--exclude (seq-map (lambda (elt)
>> +                                (if (funcall pred elt)
>> +                                    elt
>> +                                  'seq--exclude))
>> +                              seq)))
>
> This won't do the right thing if the list includes the symbol
> `seq--exclude' (which could happen if this function is used by, say,
> completion code).  Better do a (defvar seq--exclude (make-symbol "exclude"))
> and then use the value of `seq--exclude' rather than the constant
> `seq--exclude'.

Indeed.

>
>> +  "Reduce the two-arguments function FUNCTION across SEQ, starting with INITIAL-VALUE.
>
> This first line is too long.  I guess we need to drop the
> "two-arguments" part.

Ok, I will do that.


>
>> I have renamed the library "seq" instead of "sequences".
>
> Good.
>
>> seq-doseq macro, similar to dolist.
>
> Actually seq-doseq is "unusable" on lists: it's O(N^2) instead
> of O(N).

The macro could use to "dolist" if the sequence is a list.

>
> Otherwise, it looks fine, thank you,
>
>
>         Stefan

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

> The macro could use to "dolist" if the sequence is a list.

But you'd then duplicate the code of the body, which could be
problematic, especially with nested seq-doseq loops.


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>> The macro could use to "dolist" if the sequence is a list.
>
> But you'd then duplicate the code of the body, which could be
> problematic, especially with nested seq-doseq loops.

Oh, right! Another way would be to use a function, but I tried to avoid
that. Do you have a better idea in mind?

Nico
-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Stefan Monnier]

>>> The macro could use to "dolist" if the sequence is a list.
>> But you'd then duplicate the code of the body, which could be
>> problematic, especially with nested seq-doseq loops.
> Oh, right! Another way would be to use a function, but I tried to avoid
> that. Do you have a better idea in mind?

You can change your `i' to be either an integer (for arrays) or a cons
cell (for lists).  That requires an extra "is it a list?" test at each
iteration of the loop (to know how to extract the element and to
"increment" i), but I think it's the best we can do.


        Stefan

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 42 bytes --]


Hi,

Here's a new version of the patch.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: seq.diff --]
[-- Type: text/x-patch, Size: 16072 bytes --]

diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index 35141b6..b77dd06 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,7 @@
+2014-11-24  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* emacs-lisp/seq.el: New file.
+
 2014-11-24  Stefan Monnier  <monnier@iro.umontreal.ca>
 
 	* vc/vc-hooks.el (vc-state-base-face): Don't override
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
new file mode 100644
index 0000000..fa3ad56
--- /dev/null
+++ b/lisp/emacs-lisp/seq.el
@@ -0,0 +1,222 @@
+;;; seq.el --- Sequence manipulation functions  -*- lexical-binding: t -*-
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Keywords: sequences
+
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Sequence-manipulation functions that complement basic functions
+;; provided by subr.el.
+;;
+;; All functions are prefixed with "seq-".
+;;
+;; All provided functions work on lists, strings and vectors.
+;;
+;; Functions taking a predicate or a function iterating over the
+;; sequence as argument take the function as their first argument and
+;; the sequence as their second argument.  All other functions take
+;; the sequence as their first argument.
+;;
+;; All functions are tested in test/automated/seq-tests.el
+
+;;; Code:
+
+(defmacro seq-doseq (spec &rest body)
+  "Loop over a sequence.
+Similar to `dolist' but can be applied lists, strings and vectors.
+
+Evaluate BODY with VAR bound to each element of SEQ, in turn.
+Then evaluate RESULT to get return value, default nil.
+
+\(fn (VAR SEQ [RESULT]) BODY...)"
+  (declare (indent 1) (debug ((symbolp form &optional form) body)))
+  (let ((is-list (make-symbol "is-list"))
+        (seq (make-symbol "seq"))
+        (index (make-symbol "index")))
+    `(let* ((,seq ,(cadr spec))
+            (,is-list (listp seq))
+            (,index (if ,is-list ,seq 0)))
+       (while (if ,is-list
+                  (consp ,index)
+                (< ,index (seq-length ,seq)))
+         (let ((,(car spec) (if ,is-list
+                                (car ,index)
+                              (seq-elt ,seq ,index))))
+           ,@body
+           (setq ,index (if ,is-list
+                            (cdr ,index)
+                          (+ ,index 1)))))
+       ,@(if (cddr spec)
+             `((setq ,(car spec) nil) ,@(cddr spec))))))
+
+(defun seq-drop (seq n)
+  "Return a subsequence of SEQ without its first N elements.
+The result is a sequence of the same type as SEQ."
+  (let ((length (seq-length seq)))
+    (seq-subseq seq (min n length) length)))
+
+(defun seq-take (seq n)
+  "Return a subsequence of SEQ with its first N elements.
+The result is a sequence of the same type as SEQ."
+  (seq-subseq seq 0 (min n (seq-length seq))))
+
+(defun seq-drop-while (pred seq)
+  "Return a sequence, from the first element for which (PRED element) is nil, of SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-drop seq n)))
+
+(defun seq-take-while (pred seq)
+  "Return a sequence of the successive elements for which (PRED element) is non-nil in SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-take seq n)))
+
+(defun seq-filter (pred seq)
+  "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
+  (let ((exclude (make-symbol "exclude")))
+    (delq exclude (seq-map (lambda (elt)
+                             (if (funcall pred elt)
+                                 elt
+                               exclude))
+                           seq))))
+
+(defun seq-remove (pred seq)
+  "Return a list of all the elements for which (PRED element) is nil in SEQ."
+  (seq-filter (lambda (elt) (not (funcall pred elt)))
+              seq))
+
+(defun seq-reduce (function seq initial-value)
+  "Reduce the function FUNCTION across SEQ, starting with INITIAL-VALUE.
+
+Return the result of applying FUNCTION to INITIAL-VALUE and the
+first element of SEQ, then applying FUNCTION to that result and
+the second element of SEQ, then to that result and the third
+element of SEQ, etc.
+
+If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
+  (if (seq-empty-p seq)
+      initial-value
+    (let ((acc initial-value))
+      (seq-doseq (elt seq)
+        (setq acc (funcall function acc elt)))
+      acc)))
+
+(defun seq-some-p (pred seq)
+  "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (throw 'seq--break elt)))
+    nil))
+
+(defun seq-every-p (pred seq)
+  "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (or (funcall pred elt)
+          (throw 'seq--break nil)))
+    t))
+
+(defun seq-count (pred seq)
+  "Return the number of elements for which (PRED element) in non-nil in seq."
+  (let ((count 0))
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (setq count (+ 1 count))))
+    count))
+
+(defun seq-empty-p (seq)
+  "Return non-nil if the sequence SEQ is empty, nil otherwise."
+  (= 0 (seq-length seq)))
+
+(defun seq-sort (pred seq)
+  "Return a sorted sequence comparing using PRED the elements of SEQ.
+The result is a sequence of the same type as SEQ."
+  (if (listp seq)
+      (sort (seq-copy seq) pred)
+    (let ((result (seq-sort pred (append seq nil))))
+      (cond ((stringp seq) (concat result))
+            ((vectorp seq) (vconcat result))
+            (t (error "Unsupported sequence: %s" seq))))))
+
+(defun seq-contains-p (seq elt &optional testfn)
+  "Return the first element in SEQ that equals to ELT.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+  (seq-some-p (lambda (e)
+                (funcall (or testfn #'equal) elt e))
+              seq))
+
+(defun seq-uniq (seq &optional testfn)
+  "Return a list of the elements of SEQ with duplicates removed.
+Use TESTFN to compare elements, or `equal' if TESTFN is nil."
+  (let ((result '()))
+    (seq-doseq (elt seq)
+      (unless (seq-contains-p result elt testfn)
+        (setq result (cons elt result))))
+    (nreverse result)))
+
+(defun seq-subseq (seq start &optional end)
+  "Return the subsequence of SEQ from START to END.
+If END is omitted, it defaults to the length of the sequence.
+If START or END is negative, it counts from the end."
+  (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
+        ((listp seq)
+         (let (len)
+           (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
+           (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
+           (if (> start 0) (setq seq (nthcdr start seq)))
+           (if end
+               (let ((res nil))
+                 (while (>= (setq end (1- end)) start)
+                   (push (pop seq) res))
+                 (nreverse res))
+             (seq-copy seq))))
+        (t (error "Unsupported sequence: %s" seq))))
+
+(defun seq-concatenate (type &rest seqs)
+  "Concatenate, into a sequence of type TYPE, the sequences SEQS.
+TYPE must be one of following symbols: vector, string or list.
+
+\n(fn TYPE SEQUENCE...)"
+  (pcase type
+    (`vector (apply #'vconcat seqs))
+    (`string (apply #'concat seqs))
+    (`list (apply #'append (append seqs '(nil))))
+    (t (error "Not a sequence type name: %s" type))))
+
+(defalias 'seq-copy #'copy-sequence)
+(defalias 'seq-elt #'elt)
+(defalias 'seq-reverse #'reverse)
+(defalias 'seq-length #'length)
+(defalias 'seq-do #'mapc)
+(defalias 'seq-each #'seq-do)
+(defalias 'seq-map #'mapcar)
+
+(provide 'seq)
+;;; seq.el ends here
diff --git a/test/ChangeLog b/test/ChangeLog
index d0988e4..776963a 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,7 @@
+2014-11-24  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* automated/seq-tests.el: New file.
+
 2014-11-21  Ulf Jasper  <ulf.jasper@web.de>
 
 	* automated/libxml-tests.el
diff --git a/test/automated/seq-tests.el b/test/automated/seq-tests.el
new file mode 100644
index 0000000..31a05ac
--- /dev/null
+++ b/test/automated/seq-tests.el
@@ -0,0 +1,177 @@
+;;; seq-tests.el --- Tests for sequences.el
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Tests for sequences.el
+
+;;; Code:
+
+(require 'ert)
+(require 'seq)
+
+(defmacro with-test-sequences (spec &rest body)
+  "Successively bind VAR to a list, vector, and string built from SEQ.
+Evaluate BODY for each created sequence.
+
+\(fn (var seq) body)"
+  (declare (indent 1) (debug ((symbolp form) body)))
+  (let ((initial-seq (make-symbol "initial-seq")))
+    `(let ((,initial-seq ,(cadr spec)))
+       ,@(mapcar (lambda (s)
+                   `(let ((,(car spec) (apply (function ,s) ,initial-seq)))
+                      ,@body))
+                 '(list vector string)))))
+
+(defun same-contents-p (seq1 seq2)
+  "Return t if SEQ1 and SEQ2 have the same contents, nil otherwise."
+  (equal (append seq1 '()) (append seq2 '())))
+
+(defun test-sequences-evenp (integer)
+  "Return t if INTEGER is even."
+  (eq (logand integer 1) 0))
+
+(defun test-sequences-oddp (integer)
+  "Return t if INTEGER is odd."
+  (not (test-sequences-evenp integer)))
+
+(ert-deftest test-seq-drop ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (equal (seq-drop seq 0) seq))
+    (should (equal (seq-drop seq 1) (seq-subseq seq 1)))
+    (should (equal (seq-drop seq 2) (seq-subseq seq 2)))
+    (should (seq-empty-p (seq-drop seq 4)))
+    (should (seq-empty-p (seq-drop seq 10))))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p (seq-drop seq 0)))
+    (should (seq-empty-p (seq-drop seq 1)))))
+
+(ert-deftest test-seq-take ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (seq-empty-p (seq-take seq 0)))
+    (should (= (seq-length (seq-take seq 1)) 1))
+    (should (= (seq-elt (seq-take seq 1) 0) 2))
+    (should (same-contents-p (seq-take seq 3) '(2 3 4)))
+    (should (equal (seq-take seq 10) seq))))
+
+(ert-deftest test-seq-filter ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-filter #'test-sequences-evenp seq) '(6 8 10)))
+    (should (equal (seq-filter #'test-sequences-oddp seq) '(7 9)))
+    (should (equal (seq-filter (lambda (elt) nil) seq) '())))
+  (with-test-sequences (seq '())
+    (should (equal (seq-filter #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-remove ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-remove #'test-sequences-evenp seq) '(7 9)))
+    (should (equal (seq-remove #'test-sequences-oddp seq) '(6 8 10)))
+    (should (same-contents-p (seq-remove (lambda (elt) nil) seq) seq)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-remove #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-count ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-count #'test-sequences-evenp seq) 3))
+    (should (equal (seq-count #'test-sequences-oddp seq) 2))
+    (should (equal (seq-count (lambda (elt) nil) seq) 0)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-count #'test-sequences-evenp seq) 0))))
+
+(ert-deftest test-seq-reduce ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (= (seq-reduce #'+ seq 0) 10))
+    (should (= (seq-reduce #'+ seq 5) 15)))
+  (with-test-sequences (seq '())
+    (should (eq (seq-reduce #'+ seq 0) 0))
+    (should (eq (seq-reduce #'+ seq 7) 7))))
+
+(ert-deftest test-seq-some-p ()
+  (with-test-sequences (seq '(4 3 2 1))
+    (should (= (seq-some-p #'test-sequences-evenp seq) 4))
+    (should (= (seq-some-p #'test-sequences-oddp seq) 3))
+    (should-not (seq-some-p (lambda (elt) (> elt 10)) seq)))
+  (with-test-sequences (seq '())
+    (should-not (seq-some-p #'test-sequences-oddp seq))))
+
+(ert-deftest test-seq-contains-p ()
+  (with-test-sequences (seq '(3 4 5 6))
+    (should (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq 7)))
+  (with-test-sequences (seq '())
+    (should-not (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq nil))))
+
+(ert-deftest test-seq-every-p ()
+  (with-test-sequences (seq '(43 54 22 1))
+    (should (seq-every-p (lambda (elt) t) seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq))
+    (should-not (seq-every-p #'test-sequences-evenp seq)))
+  (with-test-sequences (seq '(42 54 22 2))
+    (should (seq-every-p #'test-sequences-evenp seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq)))
+  (with-test-sequences (seq '())
+    (should (seq-every-p #'identity seq))
+    (should (seq-every-p #'test-sequences-evenp seq))))
+
+(ert-deftest test-seq-empty-p ()
+  (with-test-sequences (seq '(0))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '(0 1 2))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p seq))))
+
+(ert-deftest test-seq-sort ()
+  (should (equal (seq-sort #'< "cbaf") "abcf"))
+  (should (equal (seq-sort #'< '(2 1 9 4)) '(1 2 4 9)))
+  (should (equal (seq-sort #'< [2 1 9 4]) [1 2 4 9]))
+  (should (equal (seq-sort #'< "") "")))
+
+(ert-deftest test-seq-uniq ()
+  (with-test-sequences (seq '(2 4 6 8 6 4 3))
+    (should (equal (seq-uniq seq) '(2 4 6 8 3))))
+  (with-test-sequences (seq '(3 3 3 3 3))
+    (should (equal (seq-uniq seq) '(3))))
+  (with-test-sequences (seq '())
+    (should (equal (seq-uniq seq) '()))))
+
+(ert-deftest test-seq-subseq ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (equal (seq-subseq seq 0 4) seq))
+    (should (same-contents-p (seq-subseq seq 2 4) '(4 5)))
+    (should (same-contents-p (seq-subseq seq 1 3) '(3 4)))
+    (should (same-contents-p (seq-subseq seq 1 -1) '(3 4))))
+  (should (vectorp (seq-subseq [2 3 4 5] 2)))
+  (should (stringp (seq-subseq "foo" 2 3)))
+  (should (listp (seq-subseq '(2 3 4 4) 2 3))))
+
+(ert-deftest test-seq-concatenate ()
+  (with-test-sequences (seq '(2 4 6))
+    (should (equal (seq-concatenate 'string seq [8]) (string 2 4 6 8)))
+    (should (equal (seq-concatenate 'list seq '(8 10)) '(2 4 6 8 10)))
+    (should (equal (seq-concatenate 'vector seq '(8 10)) [2 4 6 8 10]))
+    (should (equal (seq-concatenate 'vector nil '(8 10)) [8 10]))
+    (should (equal (seq-concatenate 'vector seq nil) [2 4 6]))))
+
+(provide 'seq-tests)
+;;; seq-tests.el ends here

[-- Attachment #3: Type: text/plain, Size: 854 bytes --]


I fixed all the byte-compile warnings, added an alias for `reverse', and
improved `seq-doseq'.

Stefan, can you have another look at seq-doseq?

Cheers,
Nico

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

>>>> The macro could use to "dolist" if the sequence is a list.
>>> But you'd then duplicate the code of the body, which could be
>>> problematic, especially with nested seq-doseq loops.
>> Oh, right! Another way would be to use a function, but I tried to avoid
>> that. Do you have a better idea in mind?
>
> You can change your `i' to be either an integer (for arrays) or a cons
> cell (for lists).  That requires an extra "is it a list?" test at each
> iteration of the loop (to know how to extract the element and to
> "increment" i), but I think it's the best we can do.
>
>
>         Stefan

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: [PATCH] sequence manipulation functions

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 42 bytes --]

There was an error in my previous patch.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: seq.diff --]
[-- Type: text/x-patch, Size: 16073 bytes --]

diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index 35141b6..b77dd06 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,7 @@
+2014-11-24  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* emacs-lisp/seq.el: New file.
+
 2014-11-24  Stefan Monnier  <monnier@iro.umontreal.ca>
 
 	* vc/vc-hooks.el (vc-state-base-face): Don't override
diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
new file mode 100644
index 0000000..af90c1e
--- /dev/null
+++ b/lisp/emacs-lisp/seq.el
@@ -0,0 +1,222 @@
+;;; seq.el --- Sequence manipulation functions  -*- lexical-binding: t -*-
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Keywords: sequences
+
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Sequence-manipulation functions that complement basic functions
+;; provided by subr.el.
+;;
+;; All functions are prefixed with "seq-".
+;;
+;; All provided functions work on lists, strings and vectors.
+;;
+;; Functions taking a predicate or a function iterating over the
+;; sequence as argument take the function as their first argument and
+;; the sequence as their second argument.  All other functions take
+;; the sequence as their first argument.
+;;
+;; All functions are tested in test/automated/seq-tests.el
+
+;;; Code:
+
+(defmacro seq-doseq (spec &rest body)
+  "Loop over a sequence.
+Similar to `dolist' but can be applied lists, strings and vectors.
+
+Evaluate BODY with VAR bound to each element of SEQ, in turn.
+Then evaluate RESULT to get return value, default nil.
+
+\(fn (VAR SEQ [RESULT]) BODY...)"
+  (declare (indent 1) (debug ((symbolp form &optional form) body)))
+  (let ((is-list (make-symbol "is-list"))
+        (seq (make-symbol "seq"))
+        (index (make-symbol "index")))
+    `(let* ((,seq ,(cadr spec))
+            (,is-list (listp ,seq))
+            (,index (if ,is-list ,seq 0)))
+       (while (if ,is-list
+                  (consp ,index)
+                (< ,index (seq-length ,seq)))
+         (let ((,(car spec) (if ,is-list
+                                (car ,index)
+                              (seq-elt ,seq ,index))))
+           ,@body
+           (setq ,index (if ,is-list
+                            (cdr ,index)
+                          (+ ,index 1)))))
+       ,@(if (cddr spec)
+             `((setq ,(car spec) nil) ,@(cddr spec))))))
+
+(defun seq-drop (seq n)
+  "Return a subsequence of SEQ without its first N elements.
+The result is a sequence of the same type as SEQ."
+  (let ((length (seq-length seq)))
+    (seq-subseq seq (min n length) length)))
+
+(defun seq-take (seq n)
+  "Return a subsequence of SEQ with its first N elements.
+The result is a sequence of the same type as SEQ."
+  (seq-subseq seq 0 (min n (seq-length seq))))
+
+(defun seq-drop-while (pred seq)
+  "Return a sequence, from the first element for which (PRED element) is nil, of SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-drop seq n)))
+
+(defun seq-take-while (pred seq)
+  "Return a sequence of the successive elements for which (PRED element) is non-nil in SEQ.
+The result is a sequence of the same type as SEQ."
+  (let ((n 0))
+    (while (and (< n (seq-length seq))
+                (funcall pred (seq-elt seq n)))
+      (setq n (+ 1 n)))
+    (seq-take seq n)))
+
+(defun seq-filter (pred seq)
+  "Return a list of all the elements for which (PRED element) is non-nil in SEQ."
+  (let ((exclude (make-symbol "exclude")))
+    (delq exclude (seq-map (lambda (elt)
+                             (if (funcall pred elt)
+                                 elt
+                               exclude))
+                           seq))))
+
+(defun seq-remove (pred seq)
+  "Return a list of all the elements for which (PRED element) is nil in SEQ."
+  (seq-filter (lambda (elt) (not (funcall pred elt)))
+              seq))
+
+(defun seq-reduce (function seq initial-value)
+  "Reduce the function FUNCTION across SEQ, starting with INITIAL-VALUE.
+
+Return the result of applying FUNCTION to INITIAL-VALUE and the
+first element of SEQ, then applying FUNCTION to that result and
+the second element of SEQ, then to that result and the third
+element of SEQ, etc.
+
+If SEQ is empty, return INITIAL-VALUE and FUNCTION is not called."
+  (if (seq-empty-p seq)
+      initial-value
+    (let ((acc initial-value))
+      (seq-doseq (elt seq)
+        (setq acc (funcall function acc elt)))
+      acc)))
+
+(defun seq-some-p (pred seq)
+  "Return any element for which (PRED element) is non-nil in SEQ, nil otherwise."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (throw 'seq--break elt)))
+    nil))
+
+(defun seq-every-p (pred seq)
+  "Return non-nil if (PRED element) is non-nil for all elements of the sequence SEQ."
+  (catch 'seq--break
+    (seq-doseq (elt seq)
+      (or (funcall pred elt)
+          (throw 'seq--break nil)))
+    t))
+
+(defun seq-count (pred seq)
+  "Return the number of elements for which (PRED element) in non-nil in seq."
+  (let ((count 0))
+    (seq-doseq (elt seq)
+      (when (funcall pred elt)
+        (setq count (+ 1 count))))
+    count))
+
+(defun seq-empty-p (seq)
+  "Return non-nil if the sequence SEQ is empty, nil otherwise."
+  (= 0 (seq-length seq)))
+
+(defun seq-sort (pred seq)
+  "Return a sorted sequence comparing using PRED the elements of SEQ.
+The result is a sequence of the same type as SEQ."
+  (if (listp seq)
+      (sort (seq-copy seq) pred)
+    (let ((result (seq-sort pred (append seq nil))))
+      (cond ((stringp seq) (concat result))
+            ((vectorp seq) (vconcat result))
+            (t (error "Unsupported sequence: %s" seq))))))
+
+(defun seq-contains-p (seq elt &optional testfn)
+  "Return the first element in SEQ that equals to ELT.
+Equality is defined by TESTFN if non-nil or by `equal' if nil."
+  (seq-some-p (lambda (e)
+                (funcall (or testfn #'equal) elt e))
+              seq))
+
+(defun seq-uniq (seq &optional testfn)
+  "Return a list of the elements of SEQ with duplicates removed.
+Use TESTFN to compare elements, or `equal' if TESTFN is nil."
+  (let ((result '()))
+    (seq-doseq (elt seq)
+      (unless (seq-contains-p result elt testfn)
+        (setq result (cons elt result))))
+    (nreverse result)))
+
+(defun seq-subseq (seq start &optional end)
+  "Return the subsequence of SEQ from START to END.
+If END is omitted, it defaults to the length of the sequence.
+If START or END is negative, it counts from the end."
+  (cond ((or (stringp seq) (vectorp seq)) (substring seq start end))
+        ((listp seq)
+         (let (len)
+           (and end (< end 0) (setq end (+ end (setq len (seq-length seq)))))
+           (if (< start 0) (setq start (+ start (or len (setq len (seq-length seq))))))
+           (if (> start 0) (setq seq (nthcdr start seq)))
+           (if end
+               (let ((res nil))
+                 (while (>= (setq end (1- end)) start)
+                   (push (pop seq) res))
+                 (nreverse res))
+             (seq-copy seq))))
+        (t (error "Unsupported sequence: %s" seq))))
+
+(defun seq-concatenate (type &rest seqs)
+  "Concatenate, into a sequence of type TYPE, the sequences SEQS.
+TYPE must be one of following symbols: vector, string or list.
+
+\n(fn TYPE SEQUENCE...)"
+  (pcase type
+    (`vector (apply #'vconcat seqs))
+    (`string (apply #'concat seqs))
+    (`list (apply #'append (append seqs '(nil))))
+    (t (error "Not a sequence type name: %s" type))))
+
+(defalias 'seq-copy #'copy-sequence)
+(defalias 'seq-elt #'elt)
+(defalias 'seq-reverse #'reverse)
+(defalias 'seq-length #'length)
+(defalias 'seq-do #'mapc)
+(defalias 'seq-each #'seq-do)
+(defalias 'seq-map #'mapcar)
+
+(provide 'seq)
+;;; seq.el ends here
diff --git a/test/ChangeLog b/test/ChangeLog
index d0988e4..776963a 100644
--- a/test/ChangeLog
+++ b/test/ChangeLog
@@ -1,3 +1,7 @@
+2014-11-24  Nicolas Petton <petton.nicolas@gmail.com>
+
+	* automated/seq-tests.el: New file.
+
 2014-11-21  Ulf Jasper  <ulf.jasper@web.de>
 
 	* automated/libxml-tests.el
diff --git a/test/automated/seq-tests.el b/test/automated/seq-tests.el
new file mode 100644
index 0000000..31a05ac
--- /dev/null
+++ b/test/automated/seq-tests.el
@@ -0,0 +1,177 @@
+;;; seq-tests.el --- Tests for sequences.el
+
+;; Copyright (C) 2014 Free Software Foundation, Inc.
+
+;; Author: Nicolas Petton <petton.nicolas@gmail.com>
+;; Maintainer: emacs-devel@gnu.org
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Tests for sequences.el
+
+;;; Code:
+
+(require 'ert)
+(require 'seq)
+
+(defmacro with-test-sequences (spec &rest body)
+  "Successively bind VAR to a list, vector, and string built from SEQ.
+Evaluate BODY for each created sequence.
+
+\(fn (var seq) body)"
+  (declare (indent 1) (debug ((symbolp form) body)))
+  (let ((initial-seq (make-symbol "initial-seq")))
+    `(let ((,initial-seq ,(cadr spec)))
+       ,@(mapcar (lambda (s)
+                   `(let ((,(car spec) (apply (function ,s) ,initial-seq)))
+                      ,@body))
+                 '(list vector string)))))
+
+(defun same-contents-p (seq1 seq2)
+  "Return t if SEQ1 and SEQ2 have the same contents, nil otherwise."
+  (equal (append seq1 '()) (append seq2 '())))
+
+(defun test-sequences-evenp (integer)
+  "Return t if INTEGER is even."
+  (eq (logand integer 1) 0))
+
+(defun test-sequences-oddp (integer)
+  "Return t if INTEGER is odd."
+  (not (test-sequences-evenp integer)))
+
+(ert-deftest test-seq-drop ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (equal (seq-drop seq 0) seq))
+    (should (equal (seq-drop seq 1) (seq-subseq seq 1)))
+    (should (equal (seq-drop seq 2) (seq-subseq seq 2)))
+    (should (seq-empty-p (seq-drop seq 4)))
+    (should (seq-empty-p (seq-drop seq 10))))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p (seq-drop seq 0)))
+    (should (seq-empty-p (seq-drop seq 1)))))
+
+(ert-deftest test-seq-take ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (seq-empty-p (seq-take seq 0)))
+    (should (= (seq-length (seq-take seq 1)) 1))
+    (should (= (seq-elt (seq-take seq 1) 0) 2))
+    (should (same-contents-p (seq-take seq 3) '(2 3 4)))
+    (should (equal (seq-take seq 10) seq))))
+
+(ert-deftest test-seq-filter ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-filter #'test-sequences-evenp seq) '(6 8 10)))
+    (should (equal (seq-filter #'test-sequences-oddp seq) '(7 9)))
+    (should (equal (seq-filter (lambda (elt) nil) seq) '())))
+  (with-test-sequences (seq '())
+    (should (equal (seq-filter #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-remove ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-remove #'test-sequences-evenp seq) '(7 9)))
+    (should (equal (seq-remove #'test-sequences-oddp seq) '(6 8 10)))
+    (should (same-contents-p (seq-remove (lambda (elt) nil) seq) seq)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-remove #'test-sequences-evenp seq) '()))))
+
+(ert-deftest test-seq-count ()
+  (with-test-sequences (seq '(6 7 8 9 10))
+    (should (equal (seq-count #'test-sequences-evenp seq) 3))
+    (should (equal (seq-count #'test-sequences-oddp seq) 2))
+    (should (equal (seq-count (lambda (elt) nil) seq) 0)))
+  (with-test-sequences (seq '())
+    (should (equal (seq-count #'test-sequences-evenp seq) 0))))
+
+(ert-deftest test-seq-reduce ()
+  (with-test-sequences (seq '(1 2 3 4))
+    (should (= (seq-reduce #'+ seq 0) 10))
+    (should (= (seq-reduce #'+ seq 5) 15)))
+  (with-test-sequences (seq '())
+    (should (eq (seq-reduce #'+ seq 0) 0))
+    (should (eq (seq-reduce #'+ seq 7) 7))))
+
+(ert-deftest test-seq-some-p ()
+  (with-test-sequences (seq '(4 3 2 1))
+    (should (= (seq-some-p #'test-sequences-evenp seq) 4))
+    (should (= (seq-some-p #'test-sequences-oddp seq) 3))
+    (should-not (seq-some-p (lambda (elt) (> elt 10)) seq)))
+  (with-test-sequences (seq '())
+    (should-not (seq-some-p #'test-sequences-oddp seq))))
+
+(ert-deftest test-seq-contains-p ()
+  (with-test-sequences (seq '(3 4 5 6))
+    (should (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq 7)))
+  (with-test-sequences (seq '())
+    (should-not (seq-contains-p seq 3))
+    (should-not (seq-contains-p seq nil))))
+
+(ert-deftest test-seq-every-p ()
+  (with-test-sequences (seq '(43 54 22 1))
+    (should (seq-every-p (lambda (elt) t) seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq))
+    (should-not (seq-every-p #'test-sequences-evenp seq)))
+  (with-test-sequences (seq '(42 54 22 2))
+    (should (seq-every-p #'test-sequences-evenp seq))
+    (should-not (seq-every-p #'test-sequences-oddp seq)))
+  (with-test-sequences (seq '())
+    (should (seq-every-p #'identity seq))
+    (should (seq-every-p #'test-sequences-evenp seq))))
+
+(ert-deftest test-seq-empty-p ()
+  (with-test-sequences (seq '(0))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '(0 1 2))
+    (should-not (seq-empty-p seq)))
+  (with-test-sequences (seq '())
+    (should (seq-empty-p seq))))
+
+(ert-deftest test-seq-sort ()
+  (should (equal (seq-sort #'< "cbaf") "abcf"))
+  (should (equal (seq-sort #'< '(2 1 9 4)) '(1 2 4 9)))
+  (should (equal (seq-sort #'< [2 1 9 4]) [1 2 4 9]))
+  (should (equal (seq-sort #'< "") "")))
+
+(ert-deftest test-seq-uniq ()
+  (with-test-sequences (seq '(2 4 6 8 6 4 3))
+    (should (equal (seq-uniq seq) '(2 4 6 8 3))))
+  (with-test-sequences (seq '(3 3 3 3 3))
+    (should (equal (seq-uniq seq) '(3))))
+  (with-test-sequences (seq '())
+    (should (equal (seq-uniq seq) '()))))
+
+(ert-deftest test-seq-subseq ()
+  (with-test-sequences (seq '(2 3 4 5))
+    (should (equal (seq-subseq seq 0 4) seq))
+    (should (same-contents-p (seq-subseq seq 2 4) '(4 5)))
+    (should (same-contents-p (seq-subseq seq 1 3) '(3 4)))
+    (should (same-contents-p (seq-subseq seq 1 -1) '(3 4))))
+  (should (vectorp (seq-subseq [2 3 4 5] 2)))
+  (should (stringp (seq-subseq "foo" 2 3)))
+  (should (listp (seq-subseq '(2 3 4 4) 2 3))))
+
+(ert-deftest test-seq-concatenate ()
+  (with-test-sequences (seq '(2 4 6))
+    (should (equal (seq-concatenate 'string seq [8]) (string 2 4 6 8)))
+    (should (equal (seq-concatenate 'list seq '(8 10)) '(2 4 6 8 10)))
+    (should (equal (seq-concatenate 'vector seq '(8 10)) [2 4 6 8 10]))
+    (should (equal (seq-concatenate 'vector nil '(8 10)) [8 10]))
+    (should (equal (seq-concatenate 'vector seq nil) [2 4 6]))))
+
+(provide 'seq-tests)
+;;; seq-tests.el ends here

[-- Attachment #3: Type: text/plain, Size: 989 bytes --]


Nico


Nicolas Petton <petton.nicolas@gmail.com> writes:

> Hi,
>
> Here's a new version of the patch.
>
>
> I fixed all the byte-compile warnings, added an alias for `reverse', and
> improved `seq-doseq'.
>
> Stefan, can you have another look at seq-doseq?
>
> Cheers,
> Nico
>
> Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>
>>>>> The macro could use to "dolist" if the sequence is a list.
>>>> But you'd then duplicate the code of the body, which could be
>>>> problematic, especially with nested seq-doseq loops.
>>> Oh, right! Another way would be to use a function, but I tried to avoid
>>> that. Do you have a better idea in mind?
>>
>> You can change your `i' to be either an integer (for arrays) or a cons
>> cell (for lists).  That requires an extra "is it a list?" test at each
>> iteration of the loop (to know how to extract the element and to
>> "increment" i), but I think it's the best we can do.
>>
>>
>>         Stefan

-- 
Nicolas Petton
http://nicolas-petton.fr

RE: sequence manipulation functions

[Drew Adams]

> I think these should use a "seq-" prefix.  This will not only avoid
> naming conflicts, but also helps discover those functions, since you
> can type `(seq- TAB' to see all related functions.

No.  Emacs should follow Common Lisp in this regard.
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node141.html#SECTION001800000000000000000

And it should follow it not only in terms of names but also in terms
of behavior, as much as is practical.  E.g., `some-p' should be `some',
and it should have the Common Lisp `some' behavior.

This might already be more or less the case for `cl-some' etc., in
which case there is no need (and it would be a nuisance) to add a
separate `some-p' etc. with a different behavior.

RE: sequence manipulation functions

[Artur Malabarba]

[-- Attachment #1: Type: text/plain, Size: 446 bytes --]

> > I think these should use a "seq-" prefix.  This will not only avoid
> > naming conflicts, but also helps discover those functions, since you
> > can type `(seq- TAB' to see all related functions.
>
> No.  Emacs should follow Common Lisp in this regard.
>
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node141.html#SECTION001800000000000000000
>

Could we at least add the `seq-' variants as aliases? It would greatly
improve discoverability.

[-- Attachment #2: Type: text/html, Size: 664 bytes --]

RE: sequence manipulation functions

[Drew Adams]

>> No.  Emacs should follow Common Lisp in this regard.
>> http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node141.html
>> #SECTION001800000000000000000
>
> Could we at least add the `seq-' variants as aliases?
> It would greatly improve discoverability.

Don't ask me what we "could" do.  I don't decide anything.

My own opinion would be not to do that.

If you are really worried about discoverability, then an alias
that speaks to what the function really *does* is more important
than an alias that calls out the main argument type.

`reduce' etc. are meaningful names to anyone used to functional
programming with higher-order functions, but they are not names
that help discoverability for someone not used to that.

Not to mention that the doc string for `reduce' here is not
helpful.  It just reuses the verb "reduce", without describing
anything.  Contrast the Common Lisp one-line description:

 "uses a binary operation, FUNCTION, to combine the elements of
  sequence bounded by START and END."
 (http://clhs.lisp.se/Body/f_reduce.htm)

(Yes, a one-liner is not going to make things crystal clear,
in any case.)

---

And again, we should, IMO, not introduce things like `some-p',
which overlap with `cl-some' in functionality.  Just have one
such function (for each such proposed conflict), and preferably
have it follow Common Lisp's lead.

Re: sequence manipulation functions

[Damien Cassou]

On Wed, Nov 5, 2014 at 5:25 PM, Drew Adams <drew.adams@oracle.com> wrote:
> Emacs should follow Common Lisp in this regard.

why is compatibility with Common Lisp a requirement? The main Common
Lisp functions are already available in a dedicated package.

-- 
Damien Cassou
http://damiencassou.seasidehosting.st

"Success is the ability to go from one failure to another without
losing enthusiasm."
Winston Churchill

RE: sequence manipulation functions

[Drew Adams]

> > Emacs should follow Common Lisp in this regard.
> 
> why is compatibility with Common Lisp a requirement?

No one said it is a requirement.

> The main Common Lisp functions are already available
> in a dedicated package.

Precisely.  So either we don't need this added to the
"core" or we should move those functions to the core.

It makes little sense to just add stuff that kinda-sorta
does the same thing.

Re: sequence manipulation functions

[Nicolas Petton]

I see "cl-lib" as a compatibility package with Common Lisp, not a base
library of the language. My goal is not to remove or replace "cl-lib",
but to add core sequence functions to Elisp.

Nico


Drew Adams <drew.adams@oracle.com> writes:

>> I think these should use a "seq-" prefix.  This will not only avoid
>> naming conflicts, but also helps discover those functions, since you
>> can type `(seq- TAB' to see all related functions.
>
> No.  Emacs should follow Common Lisp in this regard.
> http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node141.html#SECTION001800000000000000000
>
> And it should follow it not only in terms of names but also in terms
> of behavior, as much as is practical.  E.g., `some-p' should be `some',
> and it should have the Common Lisp `some' behavior.
>
> This might already be more or less the case for `cl-some' etc., in
> which case there is no need (and it would be a nuisance) to add a
> separate `some-p' etc. with a different behavior.

-- 
Nicolas Petton
http://nicolas-petton.fr

Re: sequence manipulation functions

[Tom Tromey]

>>>>> "Nico" == Nicolas Petton <petton.nicolas@gmail.com> writes:

Nico> I see "cl-lib" as a compatibility package with Common Lisp, not a base
Nico> library of the language. My goal is not to remove or replace "cl-lib",
Nico> but to add core sequence functions to Elisp.

But the cl- prefixes were added everywhere precisely so that regular
Emacs Lisp code could use these functions.

The `cl.el' stuff is still the compatibility layer which you're not
supposed to use.

That said, there's already a lot of duplication in elisp, so I guess
more won't hurt.

Tom

RE: sequence manipulation functions

[Drew Adams]

> there's already a lot of duplication in elisp, so I guess more won't hurt.

No, that's not a good reason to add more.  And it's not true:
duplication does not come without a cost - in particular for users,
who try to make sense of it all.

RE: sequence manipulation functions

[Drew Adams]

> I see "cl-lib" as a compatibility package with Common Lisp, not a
> base library of the language. My goal is not to remove or replace
> "cl-lib", but to add core sequence functions to Elisp.

What does that even mean?  Is dired.el core?  Is subr.el?  simple.el?

If what you mean is something that is loaded automatically, from
the outset, then the question is simple: If such functions should
be available from the outset then load them from the outset (i.e.,
add them to the "core").

What I think we do not need is to proliferate additional functions
that do pretty much the same thing.  We don't need different levels
of a function that performs a "reduce" operation, one "in the core"
and another in a library not loaded by default.

Seems like a no-brainer, to me.  (Just one opinion.)

Re: sequence manipulation functions

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > What does that even mean?  Is dired.el core?  Is subr.el?  simple.el?

All of them are in the core: their functions are documented in the manuals,
except for internal ones whose names have prefixes to avoid conflicts.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call.