[alexandria-devel] length=1
dear list, is there any objections against this? (declaim (inline length=1)) (defun length=1 (sequence) (if (listp sequence) (and sequence (null (rest sequence))) (= 1 (length sequence)))) in optimized code, where type information is available, it drops the type check. and otherwise it works for sequences and is fast for lists. maybe it could be extended into two functions: length= and length=1, where length= optimizes for lists using nthcdr. -- attila
On 2/22/08, Sean Ross <rosssd@gmail.com> wrote:
On 2/22/08, Attila Lendvai <attila.lendvai@gmail.com> wrote:
(defun length=1 (sequence)
I think something like this is always useful but would lean towards calling it singlep rather than length=1
How about LENGTH= ? ;; stupid version (defun length= (n seq) (= n (length seq))) Cheers, -- Nikodemus
On Feb 22, 2008, at 12:30, Nikodemus Siivola wrote:
How about LENGTH= ?
;; stupid version (defun length= (n seq) (= n (length seq)))
I think the idea is to have something you can use as an argument to functions like find-if. My own solution when I wanted that was functions returning closures: (defun length= (n) (lambda (seq) (= n (length seq)))) Which lets me do (find-if (length= 1) some-sequence) Cheers, -- Andreas Fuchs, (http://|im:asf@|mailto:asf@)boinkor.net, antifuchs
On Feb 22, 2008, at 12:30, Nikodemus Siivola wrote:
How about LENGTH= ?
;; stupid version (defun length= (n seq) (= n (length seq)))
I think the idea is to have something you can use as an argument to functions like find-if. My own solution when I wanted that was functions returning closures:
my need comes from cl-rdbms: it can be configured to return resultsets both as vectors and lists, and code dealing with them is full of calls to FIRST, SECOND, LENGTH=1 and friends that should work transparently on both lists and vectors. for a short moment i wanted to suggest to shadow CL:FIRST and friends in the alexandria package with unexported versions that work on generic sequences and let users :shadowing-import-from as/when they need them. that way i could forget FIRST*. but then i realized that it's kind of like a blasphemy to talk about this, so i only hypothetically mention this idea now, hoping that i won't be thrown with stones... :) so, could this survive without any vetos? there's already FIRST-ELT in sequences.lisp... but to be specific about length=1: diff -rN -u old-alexandria/sequences.lisp new-alexandria/sequences.lisp --- old-alexandria/sequences.lisp 2008-02-22 15:53:06.000000000 +0100 +++ new-alexandria/sequences.lisp 2008-02-22 15:53:06.000000000 +0100 @@ -107,9 +107,17 @@ (list (null sequence)) (sequence (zerop (length sequence))))) +(declaim (inline length=1)) +(defun length=1 (sequence) + (declare (inline sequence-of-length-p) + (optimize speed)) + (sequence-of-length-p sequence 1)) + (defun sequence-of-length-p (sequence length) "Return true if SEQUENCE is a sequence of length LENGTH. Signals an error if SEQUENCE is not a sequence. Returns FALSE for circular lists." + (declare (type array-index length) + (optimize speed)) (etypecase sequence (null (zerop length)) -- attila
On 2/22/08, Attila Lendvai <attila.lendvai@gmail.com> wrote:
but to be specific about length=1:
Hah, I had forgotten we already had SEQUENCE-OF-LENGTH-P :) In that case my only objection to length=1 is the name, which is... not ugly per se, but introduces a new naming convention. No, I don't have any good alternatives to offer straightaway. :/ Cheers, -- Nikodemus
"Nikodemus Siivola" <nikodemus@random-state.net> writes:
On 2/22/08, Attila Lendvai <attila.lendvai@gmail.com> wrote:
but to be specific about length=1:
Hah, I had forgotten we already had SEQUENCE-OF-LENGTH-P :)
In that case my only objection to length=1 is the name, which is... not ugly per se, but introduces a new naming convention. No, I don't have any good alternatives to offer straightaway. :/
Ditch SEQUENCE-OF-LENGTH-P alltogether. It's an absurdily long name for something conceptually simple. Just compare (sequence-of-length-p *foo* 1) vs. (= (length *foo*) 1) -T.
"Attila Lendvai" <attila.lendvai@gmail.com> writes:
Ditch SEQUENCE-OF-LENGTH-P alltogether. It's an absurdily long name for something conceptually simple.
it's optimized for lists
Oh, I think I articulated myself wrongly. I meant, that you should ditch the _name_ SEQUENCE-OF-LENGTH-P in favor of LENGTH=. -T.
"Attila Lendvai" <attila.lendvai@gmail.com> writes:
for a short moment i wanted to suggest to shadow CL:FIRST and friends in the alexandria package with unexported versions that work on generic sequences and let users :shadowing-import-from as/when they need them. that way i could forget FIRST*. but then i realized that it's kind of like a blasphemy to talk about this, so i only hypothetically mention this idea now, hoping that i won't be thrown with stones... :) so, could this survive without any vetos? there's already FIRST-ELT in sequences.lisp...
PJB got something like that: http://darcs.informatimago.com/darcs/public/lisp/common-lisp/generic-cl.lisp Making that a standalone library on CL.net might be a worthwhile undertaking. But something like that is out of scope of Alexandria, I think. -T.
"Attila Lendvai" <attila.lendvai@gmail.com> writes:
dear list,
is there any objections against this?
(declaim (inline length=1))
(defun length=1 (sequence) (if (listp sequence) (and sequence (null (rest sequence))) (= 1 (length sequence))))
in optimized code, where type information is available, it drops the type check. and otherwise it works for sequences and is fast for lists.
maybe it could be extended into two functions: length= and length=1, where length= optimizes for lists using nthcdr.
Yes, I favor such an inclusion. I also vote for including a LENGTH>. I've appended the definitions that I use personally below my email. There's a compiler macro for LENGTH= for when it's called with either 1 or 2, as these are the numeric arguments I've found myself to use most often. Exporting LENGTH=1 and LENGTH=2 may be debateable, the only use case is the one Andreas Fuchs mentioned, i.e. as arguments to FIND-IF &c. -T. (export '(length= length> length=1 length=2)) (defmacro optimizing-length (inline-p &body body) `(locally (declare (optimize speed) (inline length)) ,@body)) (defun length= (seq n) "Test for whether SEQ contains N number of elements. I.e. it's equivalent to (= (LENGTH SEQ) N), but besides being more concise, it may also be more efficiently implemented." (check-type n integer) (typecase seq (list (do ((i n (1- i)) (list seq (cdr list))) ((or (<= i 0) (null list)) (and (zerop i) (null list))))) (simple-vector (optimizing-length (= n (length seq)))) (vector (optimizing-length (= n (length seq)))) (sequence (optimizing-length (= n (length seq)))))) (define-compiler-macro length= (&whole form sequence n) (cond ((eql n 1) `(length=1 ,sequence)) ((eql n 2) `(length=2 ,sequence)) (t form))) (defun length> (seq n) "Returns non-nil if (> (length LIST) N)." (check-type n integer) (etypecase seq (list (and (>= n 0) (nthcdr n seq) t)) (simple-vector (optimizing-length (> (length seq) n))) (vector (optimizing-length (> (length seq) n))) (sequence (optimizing-length (> (length seq) n))))) (defun length=1 (sequence) (declare (optimize speed)) (declare (inline length)) (typecase sequence (list (and sequence (null (rest sequence)))) (simple-vector (= 1 (length sequence))) (vector (= 1 (length sequence))) (sequence (= 1 (length sequence))))) (defun length=2 (sequence) (declare (optimize speed)) (declare (inline length)) (typecase sequence (list (and sequence (cdr sequence) (null (cddr sequence)))) (simple-vector (= 2 (length sequence))) (vector (= 2 (length sequence))) (sequence (= 2 (length sequence)))))
Exporting LENGTH=1 and LENGTH=2 may be debateable, the only use case is the one Andreas Fuchs mentioned, i.e. as arguments to FIND-IF &c.
i've got this recorded and ready to be pushed. unless soemone has additional comments, i'll push it eventually. (note: i've not included the debatable length=1/2) -- attila Sat Mar 1 10:01:54 CET 2008 attila.lendvai@gmail.com * Added length>, WARNING: renamed sequence-of-length-p to length= (Based on code by Tobias C. Rittweiler) diff -rN -u old-alexandria/package.lisp new-alexandria/package.lisp --- old-alexandria/package.lisp 2008-03-01 10:02:20.000000000 +0100 +++ new-alexandria/package.lisp 2008-03-01 10:02:21.000000000 +0100 @@ -98,7 +98,8 @@ #:random-elt #:removef #:rotate - #:sequence-of-length-p + #:length= + #:length> #:shuffle #:starts-with #:starts-with-subseq diff -rN -u old-alexandria/sequences.lisp new-alexandria/sequences.lisp --- old-alexandria/sequences.lisp 2008-03-01 10:02:20.000000000 +0100 +++ new-alexandria/sequences.lisp 2008-03-01 10:02:21.000000000 +0100 @@ -1,5 +1,9 @@ (in-package :alexandria) +;; Make these inlinable by declaiming them INLINE here and some of them +;; NOTINLINE at the end of the file. +(declaim (inline copy-sequence length= length>)) + (defun rotate-tail-to-head (sequence n) (declare (type (integer 1) n)) (if (listp sequence) @@ -113,9 +117,12 @@ (list (null sequence)) (sequence (zerop (length sequence))))) -(defun sequence-of-length-p (sequence length) +(defun length= (sequence length) "Return true if SEQUENCE is a sequence of length LENGTH. Signals an error if SEQUENCE is not a sequence. Returns FALSE for circular lists." + (declare (type array-index length) + (inline length) + (optimize speed)) (etypecase sequence (null (zerop length)) @@ -123,11 +130,32 @@ (let ((n (1- length))) (unless (minusp n) (let ((tail (nthcdr n sequence))) - (and tail (null (cdr tail))))))) + (and tail + (null (cdr tail))))))) + (simple-vector + (= length (length sequence))) + (vector + (= length (length sequence))) (sequence (= length (length sequence))))) -(declaim (inline copy-sequence)) +(defun length> (sequence n) + "Returns non-nil if (> (length SEQUENCE) N)." + (declare (inline length) + (optimize speed) + (type array-index n)) + (etypecase sequence + (list + (and (>= n 0) + (nthcdr n sequence) + t)) + (simple-vector + (> (length sequence) n)) + (vector + (> (length sequence) n)) + (sequence + (> (length sequence) n)))) + (defun copy-sequence (type sequence) "Returns a fresh sequence of TYPE, which has the same elements as SEQUENCE." @@ -395,3 +423,5 @@ (setf (bit mask i) 0)))))) (derange start size) sequence))) + +(declaim (notinline length= length>))
On 3/1/08, Attila Lendvai <attila.lendvai@gmail.com> wrote:
Exporting LENGTH=1 and LENGTH=2 may be debateable, the only use case is the one Andreas Fuchs mentioned, i.e. as arguments to FIND-IF &c.
i've got this recorded and ready to be pushed. unless soemone has additional comments, i'll push it eventually.
Looks good to me. Only one comment re the ETYPECASES: I don't think it makes much sense to have a separate dispatch for SIMPLE-VECTOR cases when all we do is call LENGTH. Most implementations are going to emit identical code for (length (the vector x)) and (lenght (the simple-vector) x). Cheers, -- Nikodemus
i've got this recorded and ready to be pushed. unless soemone has additional comments, i'll push it eventually.
ok, seems like i wasn't really that happy with it after all. i almost pushed it when i tried to use it in a situation where the sequence argument was a bigger form and the literal length was lost far away in the noise. so i wanted to transpose the two arguments as the = sign in the name suggests, but obviously i couldn't. then i thought of turning length= into a function that takes &rest arguments and each argument can be either an integer or a sequence. you can find the current implementation at the end of the mail, but i'm not sure vetoers will like it... it's somewhat dwim-ish in that it accepts both integers and sequences at any position, but on the other hand anything else feels crippled from the user point of view. -- attila (defun length= (&rest sequences) "Takes any number of sequences or integers in any order. Returns true iff the length of all the sequences and the integers are equal. Hint: there's a compiler macro that expands into more efficient code if the first argument is a literal integer." (declare (dynamic-extent sequences) (inline sequence-of-length-p) (optimize speed)) (unless (cdr sequences) (error "You must call LENGTH= with at least two arguments")) ;; There's room for optimization here: multiple list arguments could be ;; traversed in parallel. (let* ((first (pop sequences)) (current (if (integerp first) first (length first)))) (declare (type array-index current)) (dolist (el sequences) (if (integerp el) (unless (= el current) (return-from length= nil)) (unless (sequence-of-length-p el current) (return-from length= nil))))) t) (define-compiler-macro length= (&whole form length &rest sequences) (cond ((zerop (length sequences)) form) (t (let ((optimizedp (integerp length))) (with-unique-names (tmp current) (declare (ignorable current)) `(locally (declare (inline sequence-of-length-p)) (let ((,tmp) ,@(unless optimizedp `((,current ,length)))) ,@(unless optimizedp `((unless (integerp ,current) (setf ,current (length ,current))))) (and ,@(loop for sequence :in sequences collect `(progn (setf ,tmp ,sequence) (if (integerp ,tmp) (= ,tmp ,(if optimizedp length current)) (sequence-of-length-p ,tmp ,(if optimizedp length current))))))))))))) some macroexpansions: DEV> (pprint (swank::compiler-macroexpand-1 `(length= 1 '(1 2)))) (LOCALLY (DECLARE (INLINE SEQUENCE-OF-LENGTH-P)) (LET ((#:TMP3027)) (AND (PROGN (SETF #:TMP3027 '(1 2)) (IF (INTEGERP #:TMP3027) (= #:TMP3027 1) (SEQUENCE-OF-LENGTH-P #:TMP3027 1)))))) ; No value DEV> (pprint (swank::compiler-macroexpand-1 `(length= '(1 2) 1))) (LOCALLY (DECLARE (INLINE SEQUENCE-OF-LENGTH-P)) (LET ((#:TMP3029) (#:CURRENT3030 '(1 2))) (UNLESS (INTEGERP #:CURRENT3030) (SETF #:CURRENT3030 (LENGTH #:CURRENT3030))) (AND (PROGN (SETF #:TMP3029 1) (IF (INTEGERP #:TMP3029) (= #:TMP3029 #:CURRENT3030) (SEQUENCE-OF-LENGTH-P #:TMP3029 #:CURRENT3030)))))) ; No value DEV>
then i thought of turning length= into a function that takes &rest arguments and each argument can be either an integer or a sequence. you can find the current implementation at the end of the mail, but i'm not sure vetoers will like it... it's somewhat dwim-ish in that it accepts both integers and sequences at any position, but on the other hand anything else feels crippled from the user point of view.
final call for vetos for length=... -- attila
then i thought of turning length= into a function that takes &rest arguments and each argument can be either an integer or a sequence. you can find the current implementation at the end of the mail, but i'm not sure vetoers will like it... it's somewhat dwim-ish in that it accepts both integers and sequences at any position, but on the other hand anything else feels crippled from the user point of view.
final call for vetos for length=...
pushed. and a simple-parse-error to conditions.lisp, too. -- attila
participants (5)
-
Andreas Fuchs -
Attila Lendvai -
Nikodemus Siivola -
Sean Ross -
Tobias C. Rittweiler