After a slight hiatus, I've finally had time to revisit partition,
making Pierre Mai's suggested change of a while back.
The updated `specification' reads like this; it's probably not clear
enough, but I hope that there's enough to be working on:
partition delimiter sequence &key :count :keep-empty-sub�
seqs :from-end :start :end :test :test-not :key
partition-if predicate sequence &key :count :keep-empty-
subseqs :from-end :start :end :key
partition-if-not predicate sequence &key :count :keep-
empty-subseqs :from-end :start :end :key
The primary return value is a list of sequences of the
same kind as the argument sequence that has elements con�
sisting of subsequences of the argument sequence that were
delimited in the argument by elements satisfying the test.
The second value is an index into the sequence indicating
the unprocessed region, suitable as an argument to subseq
to continue processing in the same manner if desired.
The :count argument, if supplied, limits the number of
subsequences in the first return value; if more than
:count delimited subsequences exist in sequence, the
:count leftmost delimited subsequences will be in order in
the first return value, and the second return value will
be the index into the sequence at which processing
stopped.
If :from-end is non-null, the argument sequence is concep�
tually processed from right to left, accumulating the sub�
sequences in reverse order; :from-end only makes a differ�
ence in the case of a non-null :count argument. In the
presence of :from-end, the :count rightmost delimited
subsequences will be in the order that they are in the
sequence argument in the first return value, and the sec�
ond is the index indicating the end of the unprocessed
region.
The :start and :end keyword arguments permit a certain
subsequence of the input sequence to be processed without
the need for a copying stage; their use is conceptually
equivalent to partitioning the subsequence delimited by
start and end, only without the need for copying.
If :keep-empty-subseqs is non-null, then empty subse�
quences will be included in the result.
In all cases, the subsequences in the first return value
will be in the order that they appeared in the original
sequence.
A reference implementation has been uploaded to cCLan
(<URL:http://cclan.sourceforge.net/>) and is also available from
<URL:http://www-jcsu.jesus.cam.ac.uk/~csr21/partition3.lisp> (earlier
versions are at ...partition{,2}.lisp for those with a sense of
history :-)
I hope that no-one finds this actively unhelpful.
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 524 842
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Thanks for your spec. It looks nice. I have two comments.
1 - As an extension I would like to propose a MPARTITION (or a
PARTITION*, a` la` CLIM) function with signature
MPARTITION delimiters sequence &key :count :keep-empty-sub�
seqs :from-end :start :end :test :test-not :key
i.e. the DELIMITERS can be a SEQUENCE of delimiters.
Of course you could implement this with PARTITION-IF, but the
different signature may allow for better algorithms.
2 - The name PARTITION is used in the context of UNION-FIND algorithms
(the LEDA library defines it so) and I have used that name for the
implemenatation that is in the CLOCC. Why not just keep the name
SPLIT?
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Thanks for your spec. It looks nice. I have two comments.
>
> 1 - As an extension I would like to propose a MPARTITION (or a
> PARTITION*, a` la` CLIM) function with signature
>
> MPARTITION delimiters sequence &key :count :keep-empty-sub�
> seqs :from-end :start :end :test :test-not :key
>
> i.e. the DELIMITERS can be a SEQUENCE of delimiters.
> Of course you could implement this with PARTITION-IF, but the
> different signature may allow for better algorithms.
I've not been tracking this, but shouldn't there be some sort of :trim
argument? e.g., :trim nil meaning give the exact partitions or
:trim '(#\Space #\Tab) meaning to remove spaces and tabs around any
delimiter.
> 2 - The name PARTITION is used in the context of UNION-FIND algorithms
> (the LEDA library defines it so) and I have used that name for the
> implemenatation that is in the CLOCC. Why not just keep the name
> SPLIT?
I definitely prefer SPLIT.
Partition also has a meaning in logic that is unwanted and that might be
separately useful on strings qua sets.
Kent M Pitman <······@world.std.com> writes:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
> > 2 - The name PARTITION is used in the context of UNION-FIND algorithms
> > (the LEDA library defines it so) and I have used that name for the
> > implemenatation that is in the CLOCC. Why not just keep the name
> > SPLIT?
>
> I definitely prefer SPLIT.
>
> Partition also has a meaning in logic that is unwanted and that might be
> separately useful on strings qua sets.
Other alternatives that have been discussed in various forums to help
Christophe find a decent name should also be mentioned:
SPLIT-SEQUENCE, DIVIDE, MUNG-SEQUENCE, REGROUP,
PUT-THINGS-FROM-THIS-SEQUENCE-INTO-SMALLER-SEQUENCES-AT-LEAST-MOST-OF-THE-TIME,
DO-STUFF-TO-SEQUENCE, BREED, DIVERSIFY, POPULATE, SPRING-FORTH,
MITOSE, FISSION, DEJOIN, (COMPLEMENT JOIN)
and a few others, but they were too serious to be mentioned.
</tongue-in-cheek>
--
------------------------------------------------------------------
Stig Erik Sandoe ····@ii.uib.no http://www.ii.uib.no/~stig/
····@ii.uib.no (Stig E. Sandoe) writes:
> Other alternatives that have been discussed in various forums to
> help Christophe find a decent name should also be mentioned:
>
> SPLIT-SEQUENCE,
This seems good.
> DIVIDE,
Math. No.
> MUNG-SEQUENCE,
Doesn't side-effect. No.
> REGROUP,
Not right because if it were thus named it would take a list of one
string into a list of many. Taking a string container of strings
and yielding a list container of strings is not a regrouping, unless
you mean multiple levels of regrouping.
Also, grouips are like sets. They don't suggest orderedness. I'd
expect (REGROUP "FOO,BAR") => ("OFO" "RBA")
No.
> PUT-THINGS-FROM-THIS-SEQUENCE-INTO-SMALLER-SEQUENCES-AT-LEAST-MOST-OF-THE-TIME,
I'm-not-big-on-names-so-long-they-run-off-the-right-margin.--When-the-
Scheme-committee-voted-for-CALL-WITH-CURRENT-CONTINUATION,-I-knew-it-was-
a-bad-omen-when-my-note-taking-had-the-damned-thing-run-into-the-right-
margin-and-have-to-turn-a-corner-the-very-first-time-time-I-wrote-it-down.
> DO-STUFF-TO-SEQUENCE,
It doesn't do stuff sequences. It doesn't even stuff them.
In some ways it unstuffs them...
No.
> BREED,
Huh? Anyway, not my bred-and-butter.
> DIVERSIFY,
Doesn't create diversity, it recognizes it. But diversity is also
non-count. I think counting is important here. I'd worry this one
would merge duplicates. It also has a bit of a hippy or equal-rights
feel to it. You're sure it wouldn't inject extra elements just to be
culturally fair, whether they were there or not? No...
> POPULATE,
Sounds like it would helpfully extend empty strings to make sure nothing
returned an empty response. And if it were called too much... no, I'm a
ZPG advocate. I have to say no to this.
> SPRING-FORTH,
Oh, yeah, sure, like the FORTH guys are gonna ad a SPRING-LISP for parity.
No free advertising here.
No.
> MITOSE,
I'm going to be a hard cell on this one. Too obscure.
> FISSION,
Sounds like a reactionary idea that will run out of control. Do this
and you're going to end up with a distinctino between fissionable
atoms and non-fissionable atoms. Hmm...
> DEJOIN,
Suggests a JOIN that doesn't exist. No...
> (COMPLEMENT JOIN)
Even moreso.
Might be cute if we didn't already have ADJOIN, but...
No, of those, I think I definitely like SPLIT-STRING.
I also would be ok with CLEAVE-STRING.
But also, STRING-LIST would be ok with me. Especially if there were
also a LIST-STRING that did (concatenate 'string ...), in just the way
that char-code and code-char work.
(STRING-LIST "foo,bar") => ("foo" "bar")
(LIST-STRING '("foo" "bar")) => "foo,bar"
For the msot part, though, this doesn't have to just work on strings
if it's properly named. That would argue for none of SPLIT-STRING,
CLEAVE-STRING, or STRING-LIST/LIST-STRING. Perhaps SPLIT-SEQUENCE,
CLEAVE-SEQUENCE, or SEQUENCE-LIST/LIST-SEQUENCE.
Kent M Pitman <······@world.std.com> wrote:
+---------------
| (STRING-LIST "foo,bar") => ("foo" "bar")
| (LIST-STRING '("foo" "bar")) => "foo,bar"
|
| For the msot part, though, this doesn't have to just work on strings
| if it's properly named. That would argue for none of SPLIT-STRING,
| CLEAVE-STRING, or STRING-LIST/LIST-STRING. Perhaps SPLIT-SEQUENCE,
| CLEAVE-SEQUENCE, or SEQUENCE-LIST/LIST-SEQUENCE.
+---------------
Hmmm... What about SPLICE-SEQUENCE or JOIN-SEQUENCE to go with "cleave":
(CLEAVE-SEQUENCE "foo,bar") => ("foo" "bar")
(SPLICE-SEQUENCE '("foo" "bar")) => "foo,bar"
Which would also allow:
(SPLICE-SEQUENCE '("foo" "bar" "baz") :delim ", ")
=> "foo, bar, baz"
[I know, that's treading perilously close to something that might be
better do with FORMAT's conditional expressions, as in the example at
the bottom of CLHS 22.3.7.2.]
-Rob
-----
Rob Warnock, 31-2-510 <····@sgi.com>
SGI Network Engineering <http://reality.sgi.com/rpw3/> [until 8/15]
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: ·········@sgi.com and ········@sgi.com aren't for humans ]
····@rigden.engr.sgi.com (Rob Warnock) writes:
> Kent M Pitman <······@world.std.com> wrote:
> +---------------
> | (STRING-LIST "foo,bar") => ("foo" "bar")
> | (LIST-STRING '("foo" "bar")) => "foo,bar"
> |
> | For the msot part, though, this doesn't have to just work on strings
> | if it's properly named. That would argue for none of SPLIT-STRING,
> | CLEAVE-STRING, or STRING-LIST/LIST-STRING. Perhaps SPLIT-SEQUENCE,
> | CLEAVE-SEQUENCE, or SEQUENCE-LIST/LIST-SEQUENCE.
> +---------------
>
> Hmmm... What about SPLICE-SEQUENCE or JOIN-SEQUENCE to go with "cleave":
Just one thing to consider when you have these names -- do you not
find names of the form CLEAVE-SEQUENCE-IF-NOT hideously ugly? I could
go with SPLIT, or CLEAVE, I guess; hey, if the thing that's most wrong
with this spec is the name then I'm probably winning :-)
> (CLEAVE-SEQUENCE "foo,bar") => ("foo" "bar")
> (SPLICE-SEQUENCE '("foo" "bar")) => "foo,bar"
>
> Which would also allow:
>
> (SPLICE-SEQUENCE '("foo" "bar" "baz") :delim ", ")
> => "foo, bar, baz"
>
> [I know, that's treading perilously close to something that might be
> better do with FORMAT's conditional expressions, as in the example at
> the bottom of CLHS 22.3.7.2.]
Firstly, there should be more than one way to do it even if there
currently isn't. Secondly, this doesn't just work on strings, where
format nil does.
Oh, what fun!
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 524 842
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Kent M Pitman wrote:
>I definitely prefer SPLIT.
I'm for SPLIT or SPLIT-SEQUENCE.
My own is named STRSPLIT but that ugly name derived from old clib habits
of our surrounding string lib funcs. formerly I called it STRTOK.
("tokenize")
STRING-LIST may be mixed up with STRING->LIST which returns the single
characters (or integers on simplier lisps).
--
perl:
split /PATTERN/,EXPR,LIMIT
Splits a string into a list of strings and returns that list. By
default, empty leading fields are preserved, and empty trailing ones
are deleted.
there's no builtin cycling string tokenizer.
php:
split(), explode() and strtok(), where strtok() comes closest (return
no list, cycle through it) and split() uses regex delims. there's also
preg_split() and spliti().
http://php.net/explode
http://php.net/strtok
http://php.net/split
--
Reini Urban
http://tv.mur.at/film/
······@x-ray.at (Reini Urban) writes:
> STRING-LIST may be mixed up with STRING->LIST which returns the single
> characters (or integers on simplier lisps).
Lisp has no such function, but I suppose yes, there's some potential confusion
with (coerce string 'list), yes.
Then again, one of the problems with coerce back and forth here is that the
possible operations are many->many. STRING->LIST has no more entitlement to
the name than anyone else. That's one reason why there's an eternal fuss over
(COERCE NIL 'STRING) vs (STRING NIL)
> perl:
> split /PATTERN/,EXPR,LIMIT
>
> Splits a string into a list of strings and returns that list. By
> default, empty leading fields are preserved, and empty trailing ones
> are deleted.
> there's no builtin cycling string tokenizer.
This seems to me a good argument for calling it SPLIT. It might not do
the same in Lisp but at least people might find it.
Kent M Pitman <······@world.std.com> writes:
> > perl:
> > split /PATTERN/,EXPR,LIMIT
> >
> > Splits a string into a list of strings and returns that list. By
> > default, empty leading fields are preserved, and empty trailing ones
> > are deleted.
> > there's no builtin cycling string tokenizer.
>
> This seems to me a good argument for calling it SPLIT. It might not do
> the same in Lisp but at least people might find it.
Right; this seems to be the consensus both here and in other forums.
So, if my specification is changed replacing every instance of
"partition" with "split", are there any other comments?
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 524 842
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > This seems to me a good argument for calling it SPLIT. It might not do
> > the same in Lisp but at least people might find it.
>
> Right; this seems to be the consensus both here and in other forums.
>
> So, if my specification is changed replacing every instance of
> "partition" with "split", are there any other comments?
It has been pointed out to me that split and split-if are used by the
series package. How does this affect the advocacy of changing
"partition" to "split"?
Yours resignedly,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > This seems to me a good argument for calling it SPLIT. It might not do
> > > the same in Lisp but at least people might find it.
> >
> > Right; this seems to be the consensus both here and in other forums.
> >
> > So, if my specification is changed replacing every instance of
> > "partition" with "split", are there any other comments?
>
> It has been pointed out to me that split and split-if are used by the
> series package. How does this affect the advocacy of changing
> "partition" to "split"?
I would use SPLIT-SEQUENCE and SPLIT-SEQUENCE-IF. In this way
it is clear that these functions work on any sequence.
I would also advocate adding the "multiple separator" spec as well.
Instead of specifying
SPLIT-SEQUENCE delimiter ....
I would either specify
SPLIT-SEQUENCE delimiters ....
where delimiters can be an ATOM or a SEQUENCE. Or add a function like
SPLIT-SEQUENCE* delimiters ...
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
Christophe Rhodes <·····@cam.ac.uk> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > This seems to me a good argument for calling it SPLIT. It might not do
> > > the same in Lisp but at least people might find it.
> >
> > Right; this seems to be the consensus both here and in other forums.
> >
> > So, if my specification is changed replacing every instance of
> > "partition" with "split", are there any other comments?
>
> It has been pointed out to me that split and split-if are used by the
> series package. How does this affect the advocacy of changing
> "partition" to "split"?
For me? It doesn't affect it at all. This is why we have packages.
Others might think differently.
"Christophe Rhodes" <·····@cam.ac.uk> wrote in message
···················@lambda.jesus.cam.ac.uk...
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > This seems to me a good argument for calling it SPLIT. It might not
do
> > > the same in Lisp but at least people might find it.
> >
> > Right; this seems to be the consensus both here and in other forums.
> >
> > So, if my specification is changed replacing every instance of
> > "partition" with "split", are there any other comments?
>
> It has been pointed out to me that split and split-if are used by the
> series package. How does this affect the advocacy of changing
> "partition" to "split"?
I vote for SPLIT-SEQUENCE.
Marc
"Marc Battyani" <·············@fractalconcept.com> writes:
> "Christophe Rhodes" <·····@cam.ac.uk> wrote in message
> ···················@lambda.jesus.cam.ac.uk...
> > Christophe Rhodes <·····@cam.ac.uk> writes:
> >
> > > Kent M Pitman <······@world.std.com> writes:
> > >
> > > > This seems to me a good argument for calling it SPLIT. It might not
> do
> > > > the same in Lisp but at least people might find it.
> > >
> > > Right; this seems to be the consensus both here and in other forums.
> > >
> > > So, if my specification is changed replacing every instance of
> > > "partition" with "split", are there any other comments?
> >
> > It has been pointed out to me that split and split-if are used by the
> > series package. How does this affect the advocacy of changing
> > "partition" to "split"?
>
> I vote for SPLIT-SEQUENCE.
Although I've said I don't mind having a package split (pardon the pun)
settle this, I also can live with SPLIT-SEQUENCE. But it would be namingwise
irregular to all the other string functions.
I'd almost prefer CLEAVE because it's shorter, even if it's harder to find.
As someone pointed out, with the -if and -if-not names, it gets pretty long
if you start puting things like -SEQUENCE in. At minimum, use -SEQ a la
COPY-SEQ.
Even so, I won't put up a big fuss whatever the outcome.
"Kent M Pitman" <······@world.std.com> wrote in message
····················@world.std.com...
> > I vote for SPLIT-SEQUENCE.
>
> Although I've said I don't mind having a package split (pardon the pun)
> settle this, I also can live with SPLIT-SEQUENCE. But it would be
namingwise
> irregular to all the other string functions.
>
> I'd almost prefer CLEAVE because it's shorter, even if it's harder to
find.
> As someone pointed out, with the -if and -if-not names, it gets pretty
long
> if you start puting things like -SEQUENCE in. At minimum, use -SEQ a la
> COPY-SEQ.
>
> Even so, I won't put up a big fuss whatever the outcome.
>
I would vote for split-seq
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> I would vote for split-seq
Hmm.
I remain unconvinced by the legion clamouring for a name change from
partition, to be honest. I think that anything I choose will either
clash with something else or be hideously ugly (or both, of course);
so I'm going to stick to my guns and go with PARTITION. Sorry if that
makes the code or the specification unuseable by anyone.
Just to recap, the current code and spec are available in a cCLan
package (apt line
deb http://www-jcsu.jesus.cam.ac.uk/ftp/pub/debian local lisp
for debian users,
<URL:http://www-jcsu.jesus.cam.ac.uk/ftp/pub/debian/lisp/source/cl-partition_20010702.tar.gz>
for those who haven't yet seen the light).
On that note, I feel I should make a (disinterested) appeal for help
for the cCLan effort; essentially, Debian users are currently
well-served, as for them installing a fair few lisp libraries and
applications is simply an apt-get away; people working on cCLan are,
however, aware that Debian Linux is not the entire world, and would
love to make their work available to more people; however, since the
people currently working on cCLan use Debian Linux almost exclusively,
this is not terribly easy...
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> "Coby Beck" <·····@mercury.bc.ca> writes:
>
> > I would vote for split-seq
>
> Hmm.
>
> I remain unconvinced by the legion clamouring for a name change from
> partition, to be honest. I think that anything I choose will either
> clash with something else or be hideously ugly (or both, of course);
> so I'm going to stick to my guns and go with PARTITION. Sorry if that
> makes the code or the specification unuseable by anyone.
Sorry for the late response, but I've been busy with my other life,
and hence had little time for professional interests...
In any case, while I'm the original proponent of sticking to
PARTITION, I'd like to add that I could also live with SPLIT-SEQUENCE
or maybe SPLIT-SEQ, if it mattered. In any case I agree that as long
as the name is not unduly ugly, this is probably the least problem
hindering acceptance.
> Just to recap, the current code and spec are available in a cCLan
> package (apt line
> deb http://www-jcsu.jesus.cam.ac.uk/ftp/pub/debian local lisp
> for debian users,
> <URL:http://www-jcsu.jesus.cam.ac.uk/ftp/pub/debian/lisp/source/cl-partition_20010702.tar.gz>
> for those who haven't yet seen the light).
There is one additional note, that I may have missed (if I already
raised this, just ignore me): I'd be more comfortable with the
:KEEP-EMPTY-SUBSEQS T behaviour being the default, since the current
default is information loosing, and I'm philosophically a bit
uncomfortable with this kind of option being the default. In other
words I'd prefer it if keeping empty subseqs (i.e. not collapsing
adjacent delimiters) were the default, and there was an option
:REMOVE-EMPTY-SUBSEQS or :COLLAPSE-ADJACENT-DELIMITERS, or whatever,
that defaulted to NIL.
OTOH this is no big requirement on my part, since only the default
setting is affected, hence there is no functional impact. Just
thought I should mention it.
In any case I'd like to take this opportunity to thank you for the
large amount of work and patience you have poured into this effort,
which to my knowledge is the first successful effort in a long time to
standardize on something in a community-based fashion, something which
most of us agree we need more of...
There is one further idea I'd like to tag onto this: Since there are
a number of other common utility functions like PARTITION that get
reinvented lots of times, maybe it would make sense to take your
PARTITION effort as a stepping-stone to define a COMMON-LISP-UTILITIES
package, or something similarly generic, where PARTITION and friends
could live, and which would ease the adoption of said functions into
implementations proper, where they could receive a greater amount of
integration and fine-tuning (using e.g. low-level primitives), than
they probably will if they continue as a purely separately maintained
add-on package.
This would become more interesting when the functions involved became
more implementation introspective, and hence more invasive and
unportable. This kind of standardized package might also provide the
platform for such things as the evolved version of the CLTL2
environment functionality, IIRC something on which some implementors
were working.
But especially for smaller stuff, which don't warrant their own little
standard (which makes conformance claims and package management IMHO a
bit too modular), such a common package would be interesting to have.
If there is interest for such an effort, I'd volunteer as an
(additional) editor (including test-case authoring), if desired.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"Pierre R. Mai" <····@acm.org> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
> > [partition]
>
> There is one additional note, that I may have missed (if I already
> raised this, just ignore me): I'd be more comfortable with the
> :KEEP-EMPTY-SUBSEQS T behaviour being the default, since the current
> default is information loosing, and I'm philosophically a bit
> uncomfortable with this kind of option being the default. In other
> words I'd prefer it if keeping empty subseqs (i.e. not collapsing
> adjacent delimiters) were the default, and there was an option
> :REMOVE-EMPTY-SUBSEQS or :COLLAPSE-ADJACENT-DELIMITERS, or whatever,
> that defaulted to NIL.
I don't think you've raised this before (I don't remember it,
anyway). It's a reasonable point, I suppose, particularly if PARTITION
is to be used in parsing fixed-format (CSV, for instance) data. I
shall sleep on it :-)
> There is one further idea I'd like to tag onto this: Since there are
> a number of other common utility functions like PARTITION that get
> reinvented lots of times, maybe it would make sense to take your
> PARTITION effort as a stepping-stone to define a COMMON-LISP-UTILITIES
> package, or something similarly generic, where PARTITION and friends
> could live, and which would ease the adoption of said functions into
> implementations proper, where they could receive a greater amount of
> integration and fine-tuning (using e.g. low-level primitives), than
> they probably will if they continue as a purely separately maintained
> add-on package.
Absolutely. I'm very interested by the SRFI (that's Scheme Request for
Implementation; <URL:http://srfi.schemers.org/>) process; inevitably,
the SRFIs themselves are variable in quality, but I think that the
scheme community needed something along those lines; and while I don't
think the lisp community is as poor in utilities and libraries (mostly
because our standard is bigger than theirs, nyaah nyaah nyaah) the
creative process I think is helped by discussion rather than everyone
sitting in their corner, as well as the learning process for the
well-meaning lurkers...
The SRFIs suffer slightly from the fact that they don't seem to be
implemented in many scheme implementations, which I suppose is
inevitable in a world where there are so many; this isn't a great
problem when the SRFI deals with making a set of functions to deal
with strings, say, because the reference implementation can be written
in portable RnRS scheme; threading and other similarly low-level
SRFIs, however, aren't so obviously implemented...
> This kind of standardized package might also provide the
> platform for such things as the evolved version of the CLTL2
> environment functionality, IIRC something on which some implementors
> were working.
What is this environment functionality? I don't know what you're
referring to, I'm afraid.
> But especially for smaller stuff, which don't warrant their own little
> standard (which makes conformance claims and package management IMHO a
> bit too modular), such a common package would be interesting to have.
> If there is interest for such an effort, I'd volunteer as an
> (additional) editor (including test-case authoring), if desired.
Well, I'm interested, so count me in; my slight concern in the process
so far is that I don't think that anyone connected to any of the
implementors has commented, which makes me think that perhaps I was
doing something wrong. Then again, maybe their silence implies that
they were entirely happy...
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> What is this environment functionality? I don't know what you're
> referring to, I'm afraid.
>
Section 8.5 of CLtL2. A way for macros to enquire about things in the
environment in which they are expanding. Functions like
VARIABLE-INFORMATION, DECLARATION-INFORMATION etc. It didn't make it
in the standard, presumably because it's very hard to specify
accurately.
--
Lieven Marchand <···@wyrd.be>
You can drag any rat out of the sewer and teach it to get some work done in
Perl, but you cannot teach it serious programming. Erik Naggum
"Pierre R. Mai" <····@acm.org> writes:
> But especially for smaller stuff, which don't warrant their own little
> standard (which makes conformance claims and package management IMHO a
> bit too modular), such a common package would be interesting to have.
> If there is interest for such an effort, I'd volunteer as an
> (additional) editor (including test-case authoring), if desired.
And on this note, on IRC today there was a call for "max with a key
argument". The consensus was that we want something that does the
equivalent of (car (sort ...)) only without the restrictions arising
from sort's destructive nature and without the efficiency hit of
actually sorting the sequence. As a bonus, we can return the value of
applying the key function to the `biggest' element as a second value.
The reference implementation for EXTREMIZE[1]:
(defun extremize (sequence predicate &key (key #'identity))
"Returns"
(let ((len (length sequence)))
(let* ((result (elt sequence 0))
(value (funcall key result)))
(loop for i from 1 to (1- len)
do (let ((val (funcall key (elt sequence i))))
(when (funcall test val value)
(setf value val)
(setf result (elt sequence i)))))
(values result value))))
And, of course, if your lisp allows you to do this, or if vendors want
to pick this up:
(define-compiler-macro car (&whole form arg)
(if (atom arg)
form
(if (eq (car arg) 'sort)
`(extremize ,@(cdr arg))
form)))
Comments (and a formal specification) welcome,
Cheers,
Christophe
[1] The naming-policy people may be interested to hear that the
following alternative names were proposed: MAXIMIZE, MINIMIZE,
EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> And on this note, on IRC today there was a call for "max with a key
> argument".
When I read this it immediately made me think of reduce, as in
(reduce #'max my-sequence :key #'my-key)
I suppose there might be situations where this isn't exactly what you
want (for one thing it returns the winning value that is the result of
calling my-key on something, not the original element in the
sequence).
John
·······@inetmi.com writes:
> (reduce #'max my-sequence :key #'my-key)
>
> I suppose there might be situations where this isn't exactly what you
> want (for one thing it returns the winning value that is the result of
> calling my-key on something, not the original element in the
> sequence).
Yes. (No?)
I want to be able to do, for example, "give me the most expensive car"
(extremize *all-your-cars* #'> :key #'car-price)
=> #<VEHICLE "Lamborghini Countach" {400093CF}>
Knowing its price is a poor substitute for owning it.
-dan
--
http://ww.telent.net/cliki/ - Link farm for free CL-on-Unix resources
[ superseded to fix the reference implementation, which contained an
unbound variable... :-( ]
"Pierre R. Mai" <····@acm.org> writes:
> But especially for smaller stuff, which don't warrant their own little
> standard (which makes conformance claims and package management IMHO a
> bit too modular), such a common package would be interesting to have.
> If there is interest for such an effort, I'd volunteer as an
> (additional) editor (including test-case authoring), if desired.
And on this note, on IRC today there was a call for "max with a key
argument". The consensus was that we want something that does the
equivalent of (car (sort ...)) only without the restrictions arising
from sort's destructive nature and without the efficiency hit of
actually sorting the sequence. As a bonus, we can return the value of
applying the key function to the `biggest' element as a second value.
The reference implementation for EXTREMIZE[1]:
(defun extremize (sequence predicate &key (key #'identity))
"Returns"
(let ((len (length sequence)))
(let* ((result (elt sequence 0))
(value (funcall key result)))
(loop for i from 1 to (1- len)
do (let ((val (funcall key (elt sequence i))))
(when (funcall predicate val value)
(setf value val)
(setf result (elt sequence i)))))
(values result value))))
And, of course, if your lisp allows you to do this, or if vendors want
to pick this up:
(define-compiler-macro car (&whole form arg)
(if (atom arg)
form
(if (eq (car arg) 'sort)
`(extremize ,@(cdr arg))
form)))
Comments (and a formal specification) welcome,
Cheers,
Christophe
[1] The naming-policy people may be interested to hear that the
following alternative names were proposed: MAXIMIZE, MINIMIZE,
EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
Just a quick note...
> And, of course, if your lisp allows you to do this, or if vendors want
> to pick this up:
>
> (define-compiler-macro car (&whole form arg)
> (if (atom arg)
> form
> (if (eq (car arg) 'sort)
> `(extremize ,@(cdr arg))
> form)))
This is not portably allowed, but more importantly it is wrong, since
it elides the side-effect of sort, therefore changing the semantics,
so that this is an invalid optimization... ;)
I'll take a look at extremize...
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
"Pierre R. Mai" <····@acm.org> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
>
> Just a quick note...
>
> > And, of course, if your lisp allows you to do this, or if vendors want
> > to pick this up:
> >
> > (define-compiler-macro car (&whole form arg)
> > (if (atom arg)
> > form
> > (if (eq (car arg) 'sort)
> > `(extremize ,@(cdr arg))
> > form)))
>
> This is not portably allowed, but more importantly it is wrong, since
> it elides the side-effect of sort, therefore changing the semantics,
> so that this is an invalid optimization... ;)
Mmm. I thought that sort was allowed to be side-effectful but didn't
have to be; I was working from
"destructive adj. (of an operator) capable of modifying some
program-visible aspect of one or more objects that are either explicit
arguments to the operator or that can be obtained directly or
indirectly from the global environment by the operator."
-- CLHS glossary
which seemed to me to allow but not require side-effects on sort's
argument. I'm perfectly happy to be corrected on this one.
It's wrong for other reasons, of course;
(car (sort "123" #'char-code))
and
(extremize "123" #'char-code)
aren't equivalent for at least two reasons (literal "123" and type
error...)
Cheers,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
>
> "Pierre R. Mai" <····@acm.org> writes:
>
> > Christophe Rhodes <·····@cam.ac.uk> writes:
> >
> > Just a quick note...
> >
> > > And, of course, if your lisp allows you to do this, or if vendors want
> > > to pick this up:
> > >
> > > (define-compiler-macro car (&whole form arg)
> > > (if (atom arg)
> > > form
> > > (if (eq (car arg) 'sort)
> > > `(extremize ,@(cdr arg))
> > > form)))
> >
> > This is not portably allowed, but more importantly it is wrong, since
> > it elides the side-effect of sort, therefore changing the semantics,
> > so that this is an invalid optimization... ;)
>
> Mmm. I thought that sort was allowed to be side-effectful but didn't
> have to be; I was working from
>
> "destructive adj. (of an operator) capable of modifying some
> program-visible aspect of one or more objects that are either explicit
> arguments to the operator or that can be obtained directly or
> indirectly from the global environment by the operator."
> -- CLHS glossary
I agree in the list case SORT is not required to have a side-effect.
I'm sure its not having one will create some program bugs, but those
bugs exist and are just waiting to be noticed... :-)
The definition of SORT does imply that for a vector, though, there is
a reliable in-place side-effect.
If you think the use of CAR around it will imply a list, maybe you're right.
But consider:
(defun my-sort (x)
(check-type x vector)
(locally (declare (optimize (safety 3)))
(handler-case (car x)
(error () t))))
I think this is conforming and does require a side-effect on x.
(sigh)
> which seemed to me to allow but not require side-effects on sort's
> argument. I'm perfectly happy to be corrected on this one.
>
> It's wrong for other reasons, of course;
> (car (sort "123" #'char-code))
> and
> (extremize "123" #'char-code)
> aren't equivalent for at least two reasons (literal "123" and type
> error...)
But replacing "123" with (setq y (copy-seq "123"))
yields a y that should end up sorted, after the error is sorted out.
Kent M Pitman <······@world.std.com> writes:
> The definition of SORT does imply that for a vector, though, there is
> a reliable in-place side-effect.
Ah yes, sorry. I'd missed the little paragraph at the bottom of the
CLHS entry for SORT:
"The sorting operation can be destructive in all cases. In the case of
a vector argument, this is accomplished by permuting the elements in
place. In the case of a list, the list is destructively reordered in
the same manner as for nreverse."
Bother.
> If you think the use of CAR around it will imply a list, maybe you're right.
> But consider:
>
> (defun my-sort (x)
> (check-type x vector)
> (locally (declare (optimize (safety 3)))
> (handler-case (car x)
> (error () t))))
>
> I think this is conforming and does require a side-effect on x.
> (sigh)
I agree. (Well, if you include a call to sort in there... :-)
Oh well,
Christophe
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
Christophe Rhodes <·····@cam.ac.uk> writes:
> Kent M Pitman <······@world.std.com> writes:
> > But consider:
> >
> > (defun my-sort (x)
> > (check-type x vector)
> > (locally (declare (optimize (safety 3)))
> > (handler-case (car x)
> > (error () t))))
> >
> > I think this is conforming and does require a side-effect on x.
> > (sigh)
>
> I agree. (Well, if you include a call to sort in there... :-)
Oops. :-)
In article <··············@lambda.jesus.cam.ac.uk>,
Christophe Rhodes <·····@cam.ac.uk> writes:
> (defun extremize (sequence predicate &key (key #'identity))
Nice. I've been using something like this for a while. A couple of minor
suggestions/queries, though:
1. What happens if the sequence is empty? I've been considering something
along the lines of :INITIAL-VALUE in REDUCE. It's nice to be able to
say something like
(extremize list #'> :initial-value 0)
to get "the largest integer in the list, or zero if the list is empty".
I haven't thought in detail about how this interacts with :KEY, though.
2. REDUCE (and possibly others; I haven't checked) say explicitly that "If
key is not supplied or is nil, the sequence element itself is used." It
would be nice if EXTREMIZE made the same "or is nil" guarantee.
3. I think it would probably be better if the reference implementation went
to the additional effort to ensure linear (rather than quadratic)
asymptotic time complexity when called on a list; I suspect this would
make it easier for CL implementations to adopt the reference
implementation unchanged. That said, I do see an argument for keeping
the reference implementation simple.
> [1] The naming-policy people may be interested to hear that the
> following alternative names were proposed: MAXIMIZE, MINIMIZE,
> EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
I've been using the name MOST, but it reads a little awkwardly. Then again,
I think all of these names are faintly awkward. Any takers for simply
EXTREME?
--
Aaron Crane
Aaron Crane <···········@pobox.com> wrote:
+---------------
| Christophe Rhodes <·····@cam.ac.uk> writes:
| > (defun extremize (sequence predicate &key (key #'identity))
...
| > [1] The naming-policy people may be interested to hear that the
| > following alternative names were proposed: MAXIMIZE, MINIMIZE,
| > EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
|
| I've been using the name MOST, but it reads a little awkwardly. Then again,
| I think all of these names are faintly awkward. Any takers for simply
| EXTREME?
+---------------
How about EXTREMUM, to make it a noun like MAX(imum)?
Seems more dignified than EXTREMIZE...
-Rob
-----
Rob Warnock, 31-2-510 <····@sgi.com>
SGI Network Engineering <http://reality.sgi.com/rpw3/> [until 8/15]
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
[Note: ·········@sgi.com and ········@sgi.com aren't for humans ]
····@rigden.engr.sgi.com (Rob Warnock) writes:
> Aaron Crane <···········@pobox.com> wrote:
> +---------------
> | Christophe Rhodes <·····@cam.ac.uk> writes:
> | > (defun extremize (sequence predicate &key (key #'identity))
> ...
> | > [1] The naming-policy people may be interested to hear that the
> | > following alternative names were proposed: MAXIMIZE, MINIMIZE,
> | > EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
> |
> | I've been using the name MOST, but it reads a little awkwardly.
> | Then again, I think all of these names are faintly awkward. Any
> | takers for simply EXTREME?
> +---------------
>
> How about EXTREMUM, to make it a noun like MAX(imum)?
> Seems more dignified than EXTREMIZE...
I like the name EXTREMUM both because it's guaranteed never to
collide with a name I'd want to use for myself and because it avoids
the awul, interminable -ise/-ize war.
In article <··············@fido.engr.sgi.com>,
····@rigden.engr.sgi.com (Rob Warnock) writes:
> Aaron Crane <···········@pobox.com> wrote:
> | Christophe Rhodes <·····@cam.ac.uk> writes:
> | > the following alternative names were proposed: MAXIMIZE, MINIMIZE,
> | > EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
> |
> | I've been using the name MOST, but it reads a little awkwardly. Then
> | again, I think all of these names are faintly awkward. Any takers for
> | simply EXTREME?
>
> How about EXTREMUM, to make it a noun like MAX(imum)? Seems more
> dignified than EXTREMIZE...
Yes, I like that. Christophe?
--
Aaron Crane
Aaron Crane <···········@pobox.com> writes:
> In article <··············@fido.engr.sgi.com>,
> ····@rigden.engr.sgi.com (Rob Warnock) writes:
> > Aaron Crane <···········@pobox.com> wrote:
> > | Christophe Rhodes <·····@cam.ac.uk> writes:
> > | > the following alternative names were proposed: MAXIMIZE, MINIMIZE,
> > | > EXMAXIMINIXZSE, EXTREMINATE, EXTREMISE, MORALLY-BIGGEST.
> > |
> > | I've been using the name MOST, but it reads a little awkwardly. Then
> > | again, I think all of these names are faintly awkward. Any takers for
> > | simply EXTREME?
> >
> > How about EXTREMUM, to make it a noun like MAX(imum)? Seems more
> > dignified than EXTREMIZE...
>
> Yes, I like that. Christophe?
I'll buy it. It makes sense, really, as EXTREMIZE slightly implies
either a side effect (though NEXTREMIZE would do that more) or else
that it returns another sequence (thinking by analogy to
STRING-CAPITALIZE).
EXTREMUM is fine.[1]
Now all we need to do is resolve the empty sequence case, agree
whether the reference implementation should have sensible scaling[2]
for lists, write up a formal specification and convince everyone else
that it's a good idea.
Christophe
[1] comp.lang.lisp in agreement over name of function shock. Please
don't disturb my suddenly rose-tinted view :)
[2] I'd vote yes -- I was just lazy when I wrote it -- if only because
I think that the reference implementation can have pedagogic value.
--
Jesus College, Cambridge, CB5 8BL +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/ (defun pling-dollar
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
On 05 Jul 2001 08:59:30 +0100, Christophe Rhodes wrote:
>> This seems to me a good argument for calling it SPLIT. It might not do
>> the same in Lisp but at least people might find it.
> Right; this seems to be the consensus both here and in other forums.
> So, if my specification is changed replacing every instance of
> "partition" with "split", are there any other comments?
SPLIT and SPLIT-IF are used by Series.
--
" ... I told my doctor I got all the exercise I needed being a
pallbearer for all my friends who run and do exercises!"
-- Winston Churchill
(setq reply-to
(concatenate 'string "Paul Foley " "<mycroft" '(··@) "actrix.gen.nz>"))