Hello
I needed to join strings. I wrote
three version of JOIN function.
Which one is preferable from point of good style,
efficiency, clarity etc. ?
(defun join1 (&rest strings)
(flet ((f (s)
(apply #'concatenate
(cons 'string (map 'list #'(lambda (x) (concatenate
'string x " ")) s)))))
(let* ((s (f strings))
(n (length s)))
(subseq s 0 (1- n)))))
(f strings)))
(defun join2 (&rest strings)
(let ((r "")
(need-separator 0))
(declare (type string r))
(declare (type fixnum need-separator))
(do ((s strings (cdr s)))
((null s))
(when (plusp need-separator) (setf r (concatenate 'string r " ")))
(incf need-separator)
(setf r (concatenate 'string r (car s))))
r))
(defun join3 (&rest strings)
(loop with r of-type string = ""
for s of-type string in strings
for need-separator of-type fixnum from 0
when (plusp need-separator) do (setf r (concatenate 'string r
" "))
do (setf r (concatenate 'string r s))
finally (return r)))
I'm sure your version will be much better. I'll study it
carefully if you let me know about it.
Probably COMMON LISP already has such function. I didn't find it.
I'm not knowing CLHS very well yet.
Thanks in advance
--
Vladimir Zolotych ······@eurocom.od.ua
"Vladimir V. Zolotych" <······@eurocom.od.ua> wrote in message
······················@eurocom.od.ua...
> Hello
>
> I needed to join strings. I wrote
> three version of JOIN function.
>
> Which one is preferable from point of good style,
> efficiency, clarity etc. ?
>
> (defun join1 (&rest strings)
> (flet ((f (s)
> (apply #'concatenate
> (cons 'string (map 'list #'(lambda (x) (concatenate
> 'string x " ")) s)))))
> (let* ((s (f strings))
> (n (length s)))
> (subseq s 0 (1- n)))))
> (f strings)))
>
> (defun join2 (&rest strings)
> (let ((r "")
> (need-separator 0))
> (declare (type string r))
> (declare (type fixnum need-separator))
> (do ((s strings (cdr s)))
> ((null s))
> (when (plusp need-separator) (setf r (concatenate 'string r " ")))
> (incf need-separator)
> (setf r (concatenate 'string r (car s))))
> r))
>
> (defun join3 (&rest strings)
> (loop with r of-type string = ""
> for s of-type string in strings
> for need-separator of-type fixnum from 0
> when (plusp need-separator) do (setf r (concatenate 'string r
> " "))
> do (setf r (concatenate 'string r s))
> finally (return r)))
>
> I'm sure your version will be much better. I'll study it
> carefully if you let me know about it.
>
> Probably COMMON LISP already has such function. I didn't find it.
> I'm not knowing CLHS very well yet.
>
I'm just a newbie myself, but I'll take a stab at this in hopes of learning
something.
(defun join-ex (x y)
(concatenate 'string x y))
(defun join (&rest strings)
(reduce #'join-ex strings))
How's that?
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> writes:
> > I needed to join strings. I wrote
> > three version of JOIN function.
> >
> > Which one is preferable from point of good style,
> > efficiency, clarity etc. ?
Yet another option that I haven't seen yet:
(defun join (&rest strings)
(with-output-to-string (output-string)
(princ (first strings) output-string)
(dolist (element (rest strings))
(princ " " output-string)
(princ element output-string))))
This is a technique that is more useful if you have fairly complicated
and especially non-uniform processing for each element, it is rather
overkill for something this uniform. It also works better than multiple
calls to CONCATENATE when you have a long list of things to operate on,
since each concatenate call ends up creating a new string, most of which
are then immediately discarded.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
"Vladimir V. Zolotych" <······@eurocom.od.ua> wrote in message
······················@eurocom.od.ua...
>
> I needed to join strings. I wrote
> three version of JOIN function.
>
Well, after posting two functions that use concatenate to do what
concatenate does by default, I came up with this:
(defun join (&rest strings)
(reduce #'join-ex
(append
(mapcar #'(lambda (x) (concatenate 'string x " "))
(butlast strings))
(last strings))))
(defun join-ex (x y)
(concatenate 'string x y))
Hideous, yes? My copy of Graham's ANSI CL arrived yesterday, so don't beat
me up too badly. I like Tim's (format nil...) solution, you just have to
love a language that allows so many choices to accomplish the same thing,
even if it allows you to come up with things like my little gem. Now all I
need is more time to play with the language, work wants C/C++ and
VB(shudder), the AI course last term used Prolog, and the course in
numerical methods this term uses Java of all things.
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> wrote in message
···················@corp.supernews.com...
>
> "Vladimir V. Zolotych" <······@eurocom.od.ua> wrote in message
> ······················@eurocom.od.ua...
> >
> > I needed to join strings. I wrote
> > three version of JOIN function.
> >
> Well, after posting two functions that use concatenate to do what
> concatenate does by default, I came up with this:
>
> (defun join (&rest strings)
> (reduce #'join-ex
> (append
> (mapcar #'(lambda (x) (concatenate 'string x " "))
> (butlast strings))
> (last strings))))
>
> (defun join-ex (x y)
> (concatenate 'string x y))
Ohh, what an idiot I am!!
(defun join-ex(x y)
(concatenate 'string x " " y))
(defun join (&rest strings)
(reduce #'join-ex strings))
Geoff
"Geoff Summerhayes" <·············@hNoOtSmPaAiMl.com> wrote in message
> Well, after posting two functions that use concatenate to do what
> concatenate does by default, I came up with this:
Since there was some mention in this thread about efficiency and style,
I will take this example to show how to avoid some common Lisp pitfalls
in algorithm design. The existence of convenient but expensive
functions like BUTLAST, LAST and APPEND can often lead one astray.
> (defun join (&rest strings)
> (reduce #'join-ex
> (append
> (mapcar #'(lambda (x) (concatenate 'string x " "))
> (butlast strings))
> (last strings))))
This function ends up traversing the list of strings 5 times:
1. Construct a new list of all but the last string
2. Mapcar over that list
3. Find the last element
4. Traverse and copy the results of the mapcar list in append.
5. Reduce on the results
A very simple rewrite of this function produces a much better algorithm
without even changing the general operation.
(defun join (&rest strings)
(reduce #'join-ex
(cons (first strings)
(mapcar #'(lambda (x) (concatenate 'string " " x))
(rest strings)))))
This reduces the list traversal from 5 to 2:
1. The mapcar on rest
2. The reduce on the results
Although (as other parts of the thread indicate) there may be better
solutions, I chose to use this to illustrate how thinking a little bit
about the the operations involved and the order in which things are done
can already yield nicer results.
I have recently converted a number of loops inherited from a predecessor
that had exactly the same structure. Given a list of objects and
something that was to be inserted between them, one can choose to view
the process as either treating the last element specially or treating
the first element specially. I think there is a "natural" tendency to
view the last element specially, since such lists are often written in
natural language as
1, 2, 3, 4, 5.
with the strong association of the punctuation with the preceding
element. However, recasting this as associating the inter-element
punctuation with the following element and treating the first element
and the trailing punctuation specially allows one to process the list
without the need to first figure out how many elements are there.
> (defun join-ex (x y)
> (concatenate 'string x y))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
"Thomas A. Russ" <···@sevak.isi.edu> wrote in message
····················@sevak.isi.edu...
>
> A very simple rewrite of this function produces a much better algorithm
> without even changing the general operation.
>
> (defun join (&rest strings)
> (reduce #'join-ex
> (cons (first strings)
> (mapcar #'(lambda (x) (concatenate 'string " " x))
> (rest strings)))))
>
Yes, I shuddered as I wrote it. I knew it was way too computationally
expensive. Thanks for the tips.
Geoff
----- Original Message -----
From: "Thomas A. Russ" <···@sevak.isi.edu>
Newsgroups: comp.lang.lisp
Sent: February 14, 2001 5:54 PM
Subject: Re: JOIN[1-3]
|
| Since there was some mention in this thread about efficiency and style,
| I will take this example to show how to avoid some common Lisp pitfalls
| in algorithm design. The existence of convenient but expensive
| functions like BUTLAST, LAST and APPEND can often lead one astray.
Oops! Before I go for the night, what did you think of the last one? I
reiterate it here, replacing the join-ex function with a lambda.
(defun join (&rest strings)
(reduce #'(lambda (x y) (concatenate 'string x " " y))
strings))
How the heck do you decide where to put whitespace, by the way? Is this OK?
Geoff
"Geoffrey Summerhayes" <·············@hNoOtSmPAaMil.com> writes:
> Oops! Before I go for the night, what did you think of the last one? I
> reiterate it here, replacing the join-ex function with a lambda.
>
> (defun join (&rest strings)
> (reduce #'(lambda (x y) (concatenate 'string x " " y))
> strings))
This is a nice implementation, and there's nothing wrong with it. The
only problem you might run into is that there's no way to pass in a
result buffer, so every call will cons several new strings.
If your application does this a lot, then you might want an
implementation that will let you use resourced buffers more easily.
You also might want to give it a slightly better name.
^L
Geoff Summerhayes wrote:
>
> (defun join (&rest strings)
> (reduce #'join-ex
> (append
> (mapcar #'(lambda (x) (concatenate 'string x " "))
> (butlast strings))
> (last strings))))
>
> (defun join-ex (x y)
> (concatenate 'string x y))
Thanks a lot to all. I've learned about REDUCE.
Here is my usage of it.
(defun join (&rest strings)
(reduce #'(lambda (&optional (x nil a) (y nil b))
(when (and a b) (concatenate 'string x " " y)))
strings))
--
Vladimir Zolotych ······@eurocom.od.ua
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
> Thanks a lot to all. I've learned about REDUCE.
> Here is my usage of it.
>
> (defun join (&rest strings)
> (reduce #'(lambda (&optional (x nil a) (y nil b))
> (when (and a b) (concatenate 'string x " " y)))
> strings))
Almost like my 4 lines:
(defun join (&rest strings)
(reduce #'(lambda (&optional a b)
(concatenate 'string a " " b))
strings))
As others have suggested, this is not the most efficient version, but
it does the job quite good, and is easy to understand (although the
name could be different).
Janis Dzerins
--
If million people say a stupid thing it's still a stupid thing.
Janis Dzerins <·····@latnet.lv> writes:
| "Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
|
| > Thanks a lot to all. I've learned about REDUCE.
| > Here is my usage of it.
| >
| > (defun join (&rest strings)
| > (reduce #'(lambda (&optional (x nil a) (y nil b))
| > (when (and a b) (concatenate 'string x " " y)))
| > strings))
|
| Almost like my 4 lines:
|
| (defun join (&rest strings)
| (reduce #'(lambda (&optional a b)
| (concatenate 'string a " " b))
| strings))
I'd like to point out that this version, Vladimir's version above
and Vladimir's original JOINs (at least the two of them I glanced
at) all work in different ways in the case of no parameters. I
think no one really wants the behaviour of your version, but if
Vladimir wants the behaviour of his version above, it would
probably be better implemented as
(defun join (&rest strings)
(when strings
(reduce (lambda (a b)
(concatenate 'string a " " b))
strings)))
so that the &optional + when trickery inside the loop is avoided
or if he wants the behaviour of his original JOIN implementations,
then one alternative would be
(defun join (&rest strings)
(if strings
(reduce (lambda (a b)
(concatenate 'string a " " b))
strings)
""))
--
Hannu
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
> I needed to join strings. I wrote
> three version of JOIN function.
From your post looks like concatenate is not what you need. From your
source looks like you want to make a string which contains strings
passed as parameter, but separated by spaces.
I'd suggesst looking at REDUCE. My version using it takes 4 lines (and
takes separator as a keyword argument).
(If nobody posts the answer and you still can't come up with the
solution, let me know.)
Janis Dzerins
--
If million people say a stupid thing it's still a stupid thing.
Janis Dzerins <·····@latnet.lv> writes:
> I'd suggesst looking at REDUCE. My version using it takes 4 lines (and
> takes separator as a keyword argument).
>
Nah.
(format nil "~{~A~^ ~}" strings)
Vastly increased crypticness, and it really annoys the
linguistic-purity brigade by reminding them that there's this whole
other language they need to get rid of once they've done for LOOP,
which is always a good thing.
For added annoyance value you should define some special syntax for
this, I usually go for something like:
#{nil "~{~A~^ ~}" strings}
--tim, for the campaign for linguistic impurity
Tim Bradshaw wrote:
>
> Janis Dzerins <·····@latnet.lv> writes:
>
> > I'd suggesst looking at REDUCE. My version using it takes 4 lines (and
> > takes separator as a keyword argument).
> >
>
> Nah.
>
> (format nil "~{~A~^ ~}" strings)
>
> Vastly increased crypticness, and it really annoys the
> linguistic-purity brigade by reminding them that there's this whole
> other language they need to get rid of once they've done for LOOP,
> which is always a good thing.
>
> For added annoyance value you should define some special syntax for
> this, I usually go for something like:
>
> #{nil "~{~A~^ ~}" strings}
>
> --tim, for the campaign for linguistic impurity
ROTFL!
Best thread I've read in c.l.l for several months. Please keep asking
such questions and we have plenty to learn and laugh.
I would use format, because it solves the problem in one line. But as
Tim pointed out, format and loop are linguistic impure, so I'd suggest
using with-output-to-string because it's more efficient than most
solutions with concatenate which have been posted. I think somebody had
already suggested this, so I add my version which handles zero arguments
and should work like the format versions. And it is recursive which
doesn't matter much.
-- joe, for the campaign for enlightened laziness
(defun join (&rest strings)
(if strings
(if (rest strings)
(with-output-to-string (output-string)
(princ (first strings) output-string)
(join-1 output-string (rest strings))
output-string)
(first strings))
""))
(defun join-1 (stream strings)
(when strings
(princ " " stream)
(princ (first strings) stream)
(join-1 stream (rest strings))))
"Vladimir V. Zolotych" <······@eurocom.od.ua> writes:
> I'm sure your version will be much better. I'll study it
> carefully if you let me know about it.
>
> Probably COMMON LISP already has such function. I didn't find it.
> I'm not knowing CLHS very well yet.
I don't know about better. Some people won't like the following
because it uses another little language embedded in CL but for your
entertainment:
(defun join (&rest strings)
(format nil ······@[ ~]~}" strings))
--
Lieven Marchand <···@wyrd.be>
Gla�r ok reifr skyli gumna hverr, unz sinn b��r bana.
>>>>> "Espen" == Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
Espen> ···@sevak.isi.edu (Thomas A. Russ) writes:
>> Or
>>
>> (defun join (&rest strings) (format nil "~{~A~^ ~}" strings))
Espen> Playing with format is just soo fun:
Espen> CL-USER 100 > (defun join (strings separator) (format nil
Espen> (format nil "~~{~~a~~^~a~~}" separator) strings)) JOIN
Espen> CL-USER 101 > (join '("foo" "bar" "gazonk") "-a-")
Espen> "foo-a-bar-a-gazonk"
Is there a _usable_ tutorial on FORMAT out there? Going past the
simple stuff seems Rather Daunting...
--
(concatenate 'string "cbbrowne" ·@ntlug.org")
http://www.ntlug.org/~cbbrowne/nonrdbms.html
"The only constructive theory connecting neuroscience and psychology
will arise from the study of software."
-- Alan Perlis
[To the endless aggravation of both disciplines. Ed.]
········@hex.net writes:
> >>>>> "Espen" == Espen Vestre <·····@*do-not-spam-me*.vestre.net> writes:
> Espen> ···@sevak.isi.edu (Thomas A. Russ) writes:
> >> Or
> >>
> >> (defun join (&rest strings) (format nil "~{~A~^ ~}" strings))
>
> Espen> Playing with format is just soo fun:
>
> Espen> CL-USER 100 > (defun join (strings separator) (format nil
> Espen> (format nil "~~{~~a~~^~a~~}" separator) strings)) JOIN
This cheapy version looks to me like it will screw up if separator
contains ~'s. You really need to do (quote-for-format separator)
rather than just separator in the argument to the inner format,
and, of course, you need to write quote-for-format, which would just
be something that doubles every ~ in the string.
> Espen> CL-USER 101 > (join '("foo" "bar" "gazonk") "-a-")
> Espen> "foo-a-bar-a-gazonk"
>
> Is there a _usable_ tutorial on FORMAT out there? Going past the
> simple stuff seems Rather Daunting...
You mean other than the spec? There are a bunch of examples there.
* "Vladimir V. Zolotych" <······@eurocom.od.ua>
|
| I needed to join strings. I wrote
| three version of JOIN function.
|
| Which one is preferable from point of good style,
| efficiency, clarity etc. ?
here's my suggestion:
(defun interleave (separator list)
(loop
for x on list
collect (car x)
until (null (cdr x))
collect separator))
(defun join-strings (strings &optional (separator " "))
(apply #'concatenate (cons 'string (interleave separator strings))))
I'm sure it can be done more efficiently (without consing at all), but
this is easy to read, and INTERLEAVE is useful in its own right.
--
Vebjorn
On 15 Feb 2001 00:07:06 -0800, Vebjorn Ljosa <·····@ljosa.com> wrote:
> * "Vladimir V. Zolotych" <······@eurocom.od.ua>
> |
> | I needed to join strings. I wrote
> | three version of JOIN function.
> |
> | Which one is preferable from point of good style,
> | efficiency, clarity etc. ?
>
> here's my suggestion:
>
> (defun interleave (separator list)
> (loop
> for x on list
> collect (car x)
> until (null (cdr x))
> collect separator))
Remember you can do destructuring in LOOP:
(defun interleave (separator list)
(loop
for (x . more) on list
collect x
until (not more)
collect separator))
__Jason
Vebjorn Ljosa <·····@ljosa.com> writes:
> * "Vladimir V. Zolotych" <······@eurocom.od.ua>
> |
> | I needed to join strings. I wrote
> | three version of JOIN function.
> |
> | Which one is preferable from point of good style,
> | efficiency, clarity etc. ?
>
> here's my suggestion:
>
> (defun interleave (separator list)
> (loop
> for x on list
> collect (car x)
> until (null (cdr x))
> collect separator))
>
> (defun join-strings (strings &optional (separator " "))
> (apply #'concatenate (cons 'string (interleave separator strings))))
Two points:
a) You don't need to cons the 'STRING in front of the interleaved
list, you can just pass it directly to APPLY:
(apply #'concatenate 'string (interleave separator strings))
b) Beware that the number of arguments you can pass via APPLY will be
limited by the value of CALL-ARGUMENTS-LIMIT of your
implementation. For portable programs you can only assume the
standard mandated minimum for this, which is as low as 50. There
are real-life implementations where this value is indeed as low as
50 or 255.
In situations where you can't estimate the upper bound of your
argument list (like in this case), you are better of using REDUCE
instead of APPLY, since REDUCE works by pairwise reduction, and
hence never runs into the CALL-ARGUMENTS-LIMIT. E.g.:
(defun join-strings (strings &optional (separator " "))
(flet ((string-concatenate (&rest args)
(apply #'concatenate 'string args)))
(reduce #'string-concatenate (interleave separator strings))))
Of course this takes away much of the simplicity of your solution,
so one might want to integrate the interleaving of the separator
into STRING-CONCATENATE.
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
In article <·················@eurocom.od.ua>,
Vladimir V. Zolotych <······@eurocom.od.ua> wrote:
> Hello
>
>I needed to join strings. I wrote
>three version of JOIN function.
>
>Which one is preferable from point of good style,
>efficiency, clarity etc. ?
>
Unfortunately, these points are conflicting goals quite often.
Tim Bradshaw's and Thom Russ' version is definitely the most
concise version (and also the clearest one, if you happen to
speak the format-sublanguage :-)
(defun join (&rest strings)
(format nil "~{~A~^ ~}" strings))
If you need utmost efficiency, you'd probably end up with
C-like Lisp as in the following, which happens to beat the
above by a factor of 20 when joining 1000 strings of length 1000.
One reason is that this algorithm has linear behaviour in the
number of input-strings.
(defun join (&rest strings)
(if (null strings)
""
(loop with result = (make-array (1- (loop for string in strings
sum (1+ (length string))))
:element-type 'base-char
:initial-element #\space)
for string in strings
as start = 0 then (1+ end)
as end = (+ start (length string))
do
(setf (subseq result start end) string)
finally
(return result))))
cheers, Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
--------------------------------------------------------------------------
········@hummel.cs.waikato.ac.nz (Bernhard Pfahringer) writes:
> In article <·················@eurocom.od.ua>,
> Vladimir V. Zolotych <······@eurocom.od.ua> wrote:
> > Hello
> >
> >I needed to join strings. I wrote
> >three version of JOIN function.
> >
> >Which one is preferable from point of good style,
> >efficiency, clarity etc. ?
> >
>
> Unfortunately, these points are conflicting goals quite often.
>
> Tim Bradshaw's and Thom Russ' version is definitely the most
> concise version (and also the clearest one, if you happen to
> speak the format-sublanguage :-)
>
> (defun join (&rest strings)
> (format nil "~{~A~^ ~}" strings))
>
> If you need utmost efficiency, you'd probably end up with
> C-like Lisp as in the following, which happens to beat the
> above by a factor of 20 when joining 1000 strings of length 1000.
> One reason is that this algorithm has linear behaviour in the
> number of input-strings.
>
> (defun join (&rest strings)
> (if (null strings)
> ""
> (loop with result = (make-array (1- (loop for string in strings
> sum (1+ (length string))))
> :element-type 'base-char
> :initial-element #\space)
> for string in strings
> as start = 0 then (1+ end)
> as end = (+ start (length string))
> do (setf (subseq result start end) string)
> finally (return result))))
As an aside, the
(setf (subseq result start end) string)
should also serve to point out a nice feature of CL.
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://galt.mrl.nyu.edu/valis
Like DNA, such a language [Lisp] does not go out of style.
Paul Graham, ANSI Common Lisp