What do you use to iterate over a generic sequence (in the manner of
quite a few of the "library" functions like FIND-IF)? The major
possibilities seem to be:
1. Using ELT with LOOP or DOTIMES (which seems needlessly inefficient,
especially for lists). The upside is that it's very simple.
2. Using MAP with the appropriate function. This is what I usually do.
It's a little less clear, and for all I know it really isn't that much
more efficient than the ELT solution.
3. Using something more general with closures and LOOP or DO, like so:
(defun do-stuff-with-sequence (sequence)
(let ((iterator
(etypecase sequence
(list
#'(lambda ()
(pop sequence)))
(vector
(let ((i 0)
(length (length sequence)))
#'(lambda ()
(if (= i length)
nil
(prog1
(aref sequence i)
(incf i)))))))))
(loop
:for elt := (funcall iterator)
:while elt
:do (stuff elt))))
I like option 3, but I don't recall seeing it in the wild, and there
may be something horribly wrong with it that I don't recognize. I can
see how to generalize it to have :START and :END arguments, to use
more specific ways of accessing sequence elements (like SVREF and
CHAR), and all the rest, though. It's also easy enough to pull out the
code that sets up the ITERATOR closure as function or macro.
Also, it's entirely possible that my instincts about efficiency are
totally wrong: they usually are. :-/
Cheers,
Pillsy
From: Kent M Pitman
Subject: Re: Iterating over generic sequences.
Date:
Message-ID: <ubqbpawh0.fsf@nhplace.com>
Pillsy <·········@gmail.com> writes:
> What do you use to iterate over a generic sequence (in the manner of
> quite a few of the "library" functions like FIND-IF)? The major
> possibilities seem to be:
>
> 1. Using ELT with LOOP or DOTIMES (which seems needlessly inefficient,
> especially for lists). The upside is that it's very simple.
It's also potentially O(n^2) since ELT is O(n) for lists. You do not
want to use ELT for much of anything, but most certainly you do not want
to use it for iterating across a list. Personally, I avoid ELT entirely
except for occasional light debugging or demonstration code.
> 2. Using MAP with the appropriate function. This is what I usually do.
> It's a little less clear, and for all I know it really isn't that much
> more efficient than the ELT solution.
Then make a functional or macro abstraction. This is the right technology
to iterate across a sequence since that is its precise purpose.
> 3. Using something more general with closures and LOOP or DO, like so:
Pascal wrote a solution to this, so I won't repeat that. But I just don't
see why you expect this to be better than a nice pretty call to MAP
(optionally abstracted into some other calling sequence if you know some
additional fact about return value or whatever that allows you to simplify
its notation further).
On Sep 26, 6:32 pm, Kent M Pitman <······@nhplace.com> wrote:
> Pillsy <·········@gmail.com> writes:
[...]
> > 1. Using ELT with LOOP or DOTIMES (which seems needlessly inefficient,
> > especially for lists). The upside is that it's very simple.
> It's also potentially O(n^2) since ELT is O(n) for lists. You do not
> want to use ELT for much of anything, but most certainly you do not want
> to use it for iterating across a list.
Yeah. That's the reason I never use it, but I never use it, so I
forgot why I never use it. :-/
> Pascal wrote a solution to this, so I won't repeat that. But I just don't
> see why you expect this to be better than a nice pretty call to MAP
> (optionally abstracted into some other calling sequence if you know some
> additional fact about return value or whatever that allows you to simplify
> its notation further).
The main thing that started me thinking in that direction is probably
that I was doing something where I wanted to use LOOP (and drive
multiple variables at once and do some of the other LOOPy stuff),
which tends to be pretty awkward when you're using MAP. Then I wrote
an example that totally failed to capture that.
I also find it pretty helpful to have my misguided gut feelings
thoroughly refuted.
Cheers,
Pillsy
On Sep 26, 8:47 pm, Pillsy <·········@gmail.com> wrote:
> 2. Using MAP with the appropriate function. This is what I usually do.
> It's a little less clear, and for all I know it really isn't that much
> more efficient than the ELT solution.
Then all you know isn't worth very much (on the subject of iterating
across CL sequences, at least). Think harder.
> 3. Using something more general with closures and LOOP or DO, like so:
MAP is the general sequence iterator.
On Sep 26, 4:57 pm, "Thomas F. Burdick" <········@gmail.com> wrote:
> On Sep 26, 8:47 pm, Pillsy <·········@gmail.com> wrote:
> > 2. Using MAP with the appropriate function. This is what I usually do.
> > It's a little less clear, and for all I know it really isn't that much
> > more efficient than the ELT solution.
> Then all you know isn't worth very much (on the subject of iterating
> across CL sequences, at least).
Well, it's not, but the ELT thing was actually just me being really
dumb.
Cheers,
Pillsy
Pillsy wrote:
> What do you use to iterate over a generic sequence (in the manner of
> quite a few of the "library" functions like FIND-IF)? The major
> possibilities seem to be:
>
> 1. Using ELT with LOOP or DOTIMES (which seems needlessly inefficient,
> especially for lists). The upside is that it's very simple.
>
> 2. Using MAP with the appropriate function. This is what I usually do.
> It's a little less clear, and for all I know it really isn't that much
> more efficient than the ELT solution.
>
> 3. Using something more general with closures and LOOP or DO, like so:
>
> (defun do-stuff-with-sequence (sequence)
> (let ((iterator
> (etypecase sequence
> (list
> #'(lambda ()
> (pop sequence)))
> (vector
> (let ((i 0)
> (length (length sequence)))
> #'(lambda ()
> (if (= i length)
> nil
> (prog1
> (aref sequence i)
> (incf i)))))))))
> (loop
> :for elt := (funcall iterator)
> :while elt
> :do (stuff elt))))
(defgeneric do-stuff-with-sequence (sequence)
(:method ((sequence vector))
(loop for element across sequence
do (stuff element)))
(:method ((sequence list))
(loop for element in sequence
do (stuff element))))
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/