From: Teemu Likonen
Subject: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <871voolfae.fsf@iki.fi>
It's a Common Lisp newbie here; I'm more experienced in Emacs Lisp. I
wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
(mapconcat 'identity '("one" "two" "three") "-")
=> "one-two-three"
I can do the same in CL with this:
(let ((list '("one" "two" "three")))
(format nil "~{~a-~}~a" (butlast list) (car (last list))))
But I have a feeling that there could be a more elegant way. Is there?
Teemu Likonen <········@iki.fi> writes:
> I can do the same in CL with this:
>
> (let ((list '("one" "two" "three")))
> (format nil "~{~a-~}~a" (butlast list) (car (last list))))
>
> But I have a feeling that there could be a more elegant way. Is there?
Well, there's a more elegant FORMAT solution:
(format nil "~{~a~^-~}" '("one" "two" "three"))
--
Thomas A. Russ, USC/Information Sciences Institute
From: Teemu Likonen
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <877hygs4n9.fsf@iki.fi>
On 2009-07-10 09:48 (-0700), Thomas A. Russ wrote:
> Teemu Likonen <········@iki.fi> writes:
>> I can do the same in CL with this:
>>
>> (let ((list '("one" "two" "three")))
>> (format nil "~{~a-~}~a" (butlast list) (car (last list))))
>>
>> But I have a feeling that there could be a more elegant way. Is there?
>
> Well, there's a more elegant FORMAT solution:
>
> (format nil "~{~a~^-~}" '("one" "two" "three"))
Ah, thanks. That's nice. It seems that there are tons of features in
this format function. Should be worth studying.
Thanks for Pascal too for his more general solution. I have to admit
that with my current Lisp knowledge I can't quite parse it. I understand
the idea, though.
On Jul 10, 3:46 pm, Teemu Likonen <········@iki.fi> wrote:
> On 2009-07-10 09:48 (-0700), Thomas A. Russ wrote:
[...]
> > (format nil "~{~a~^-~}" '("one" "two" "three"))
> Ah, thanks. That's nice. It seems that there are tons of features in
> this format function. Should be worth studying.
There are indeed a ton of features in that FORMAT function. There's an
excellent (though not exhaustive) discusstion of those features at
http://gigamonkeys.com/book/a-few-format-recipes.html
Cheers,
Pillsy
On Jul 10, 3:46 pm, Teemu Likonen <········@iki.fi> wrote:
> Thanks for Pascal too for his more general solution. I have to admit
> that with my current Lisp knowledge I can't quite parse it. I understand
> the idea, though.
Oddly enough, I had to write just such a function today. It's a
simple recursive solution, so it should be simple to understand,
although it only works for strings:
(defun intersperse (strs elem)
(if (null (cdr strs))
(car strs)
(concatenate 'string (car strs) elem (intersperse (cdr strs)
elem))))
Jimmy Miller <··············@gmail.com> writes:
>
> Oddly enough, I had to write just such a function today. It's a
> simple recursive solution, so it should be simple to understand,
> although it only works for strings:
>
> (defun intersperse (strs elem)
> (if (null (cdr strs))
> (car strs)
> (concatenate 'string (car strs) elem (intersperse (cdr strs)
> elem))))
I wrote a version which uses FORMAT instead:
(defun interpolate-with-format (strs elem)
(format nil (format nil "~~{~~a~~^~a~~}" elem) strs))
I then ran each version on an array of 1,024 small random strings two
dozen times. INTERPOLATE took almost two and a half times as long to
run as INTERPOLATE-WITH-FORMAT and used over 11 times as much memory.
So I'd suggest using the FORMAT solution.
--
Robert Uhl <http://public.xdi.org/=ruhl>
In poker you have to show your hand eventually if called. So far SCO
have with great reluctance shown only one card, which turned out to be
'Mr Bun, The Baker.' --Electric Dragon on groklaw.net
In article <··············@latakia.octopodial-chrome.com>,
Robert Uhl <·········@NOSPAMgmail.com> wrote:
> Jimmy Miller <··············@gmail.com> writes:
> >
> > Oddly enough, I had to write just such a function today. It's a
> > simple recursive solution, so it should be simple to understand,
> > although it only works for strings:
> >
> > (defun intersperse (strs elem)
> > (if (null (cdr strs))
> > (car strs)
> > (concatenate 'string (car strs) elem (intersperse (cdr strs)
> > elem))))
>
> I wrote a version which uses FORMAT instead:
>
> (defun interpolate-with-format (strs elem)
> (format nil (format nil "~~{~~a~~^~a~~}" elem) strs))
>
> I then ran each version on an array of 1,024 small random strings two
> dozen times. INTERPOLATE took almost two and a half times as long to
> run as INTERPOLATE-WITH-FORMAT and used over 11 times as much memory.
> So I'd suggest using the FORMAT solution.
The recursive version calls CONCATENATE to cons a new string n-1 times.
FORMAT presumably uses a more efficient buffer management strategy.
(defun intersperse-list (list item)
(if (null (cdr list))
list
(list* (car list) item
(intersperse-list (cdr list) item))))
(defun mapconcat (strs elem)
(apply #'concatenate 'string (intersperse-list strs elem)))
This will work as long as your list length is less than half of
call-argument-limits. A more robust solution would split the result of
intersperse-list into sublists of this length, concatenate each of these
sublists, and then concatenate the results (actually, you'd have to make
this recursive, in case the list is more than call-argument-limits
squared).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Here is my take on implementing what Barry Margolin proposed. (As
this is, at heart, a map/reduce problem, his suggestion allows this
kind of solution without a very bad performance hit.) One reason I am
interested in this is the opportunity to generalize `mapconcat' by
being able to specify the type of the resulting sequence. So, for
example:
(map-concatenate 'list #'list '(foo bar baz) (list '-))
=> (FOO - BAR - BAZ)
(map-concatenate 'string #'string '(foo bar baz) (string '-))
=> "FOO-BAR-BAZ"
(not just theoretical physicists like symmetries).
I also wanted to keep things sequence-generic and thus limited myself
to MAP, REDUCE, & Co.
The resulting solution is---I am tempted to say "of course"---slower
than the WRITE-STRING/WITH-OUTPUT-TO-STRING solution. This is in part
the price to pay for greater generality; in part because I saved
myself the effort or the complications of some optimizations; in part
because I did not want to spend time hand-crafting specialized
solutions for specific sequence types; and in part because this kind
of programs have a greater need for an SSC to be mechanically
optimized.
On the other hand, doing it with concatenation (as opposed to an
iteration, whether by means of MAP of NIL or FORMAT's ``~{...~}''), is
more amenable to parallelization, and this is also an example
illustrating the well-known importance of associativity of operations
(such as concatenation) in this regard. (Associativity also allows
REDUCE of ``:FROM-END T'', which may have---as in this case---a
dramatic effect on performance.)
* * *
(defun map-concatenate (type f xs s)
"Concatenate into a TYPE sequence the values of F on XS, S-separated.
For example, (MAPCONCAT F XS S) <=> (MAP-CONCATENATE 'STRING F XS S).
\"Demo\" grade."
(reduce-am #'(lambda (&rest ss) (apply #'concatenate type ss))
;; the interspersing:
(rest (reduce #'(lambda (x y) (list* s x y))
(map 'list f xs)
:from-end t :initial-value '()))))
(defun reduce-am (f xs &key (limit (- call-arguments-limit 1)))
"Reduce by F the sequence XS, with each application on LIMIT elements.
\"AM\" stands for F being associative and of multiple arguments.
\"Demo\" grade."
(cond ((not (listp xs)) (reduce-am f (coerce xs 'list)) :limit limit)
((endp (rest xs)) (apply f xs))
(t (reduce-am f (reduce-am-1-list f xs limit) :limit limit))))
(defun reduce-am-1-list (f xs limit)
"Perform one pass applying F to parts of the list XS, each LIMIT elements.
Return a list of the results. Used by REDUCE-AM. \"Demo\" grade."
;; this can be made iterative fairly easily
(multiple-value-bind (value tail) (reduce-am-1 f xs limit)
(if (endp tail) (list value)
(cons value (reduce-am-1-list f tail limit)))))
(defun reduce-am-1 (f xs limit)
"Apply F to the list XS's first LIMIT elements.
Return the result and as a second value, the remaining part of XS.
Used by REDUCE-AM-1-LIST. \"Demo\" grade."
(let ((tail (nthcdr (min limit (length xs)) xs)))
(values (apply f (ldiff xs tail)) tail)))
---Vassil.
--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
Teemu Likonen <········@iki.fi> writes:
> It's a Common Lisp newbie here; I'm more experienced in Emacs Lisp. I
> wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
>
> (mapconcat 'identity '("one" "two" "three") "-")
> => "one-two-three"
>
> I can do the same in CL with this:
>
> (let ((list '("one" "two" "three")))
> (format nil "~{~a-~}~a" (butlast list) (car (last list))))
>
> But I have a feeling that there could be a more elegant way. Is there?
Yes, write: (mapconcat 'identity '("one" "two" "three") "-") ; elegant!
Of course, with:
(defun mapconcat (fun list sep)
(when list
(let ((~sep (with-output-to-string (*standard-output*)
(map nil (lambda (ch) (princ (if (char= #\~ ch) "~~" ch))) sep))))
(format nil (format nil "~~A~~{~A~~A~~}" ~sep)
(funcall fun (first list))
(mapcar fun (rest list))))))
(mapconcat 'identity '("one" "two" "three") "-")
--> "one-two-three"
(mapconcat (lambda (x) (concatenate 'string "[" x "]")) '("one" "two" "three") "~")
--> "[one]~[two]~[three]"
--
__Pascal Bourguignon__
Teemu Likonen
> wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
>
> (mapconcat 'identity '("one" "two" "three") "-")
> => "one-two-three"
>
> I can do the same in CL with this:
>
> (let ((list '("one" "two" "three")))
> (format nil "~{~a-~}~a" (butlast list) (car (last list))))
>
> But I have a feeling that there could be a more elegant way. Is there?
>
Maybe
(defun connect-by-hyphen (x y)
(concatenate 'string x "-" y))
(reduce #'connect-by-hyphen '("one" "two" "three"))
--
Take it Easy Don't Hurry Be Happy
Thierry
�������o�o��������o�o��������o�o��������o�o��������o�o�������
On Jul 10, 4:29 pm, Thierry Pirot <····@thierrypirot.net> wrote:
> Teemu Likonen> wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
>
> > (mapconcat 'identity '("one" "two" "three") "-")
> > => "one-two-three"
>
> > I can do the same in CL with this:
>
> > (let ((list '("one" "two" "three")))
> > (format nil "~{~a-~}~a" (butlast list) (car (last list))))
>
> > But I have a feeling that there could be a more elegant way. Is there?
>
> Maybe
>
> (defun connect-by-hyphen (x y)
> (concatenate 'string x "-" y))
>
> (reduce #'connect-by-hyphen '("one" "two" "three"))
>
> --
> Take it Easy Don't Hurry Be Happy
>
> Thierry
>
> °¨¨¨¨°ºo§oº°¨¨¨¨°ºo§oº°¨¨¨¨°ºo§oº°¨¨¨¨°ºo§oº°¨¨¨¨°ºo§oº°¨¨¨¨°
I like your idea the best. More elegant than the nested formats
anyway. I would write it this way:
(defun mapconcat (str-list delim)
(reduce (lambda (x y)
(concatenate 'string x delim y))
str-list))
This NG seems to discuss this problem quite a bit. I know I myself
brought it up around 3 years ago, after reading Seibel's book. While
he does make a good case for format in general, this is one spot where
format is missing a directive.
I seem to recall once reading a ~/.../ solution from Juho Snellman
about this one. I thought it was nicer than "~~{~~A~~^~A~~}" and-
replace-the-tildes-if-need-be.
Kyle
* Kyle M <····································@d34g2000vbm.googlegroups.com> :
Wrote on Mon, 13 Jul 2009 15:43:43 -0700 (PDT):
| On Jul 10, 4:29 pm, Thierry Pirot
|> Teemu Likonen> wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
|>
|> > (mapconcat 'identity '("one" "two" "three") "-")
|> > => "one-two-three"
|>
|> (defun connect-by-hyphen (x y)
|> (concatenate 'string x "-" y))
|>
|> (reduce #'connect-by-hyphen '("one" "two" "three"))
|
|
| I like your idea the best. More elegant than the nested formats
| anyway. I would write it this way:
|
| (defun mapconcat (str-list delim)
| (reduce (lambda (x y)
| (concatenate 'string x delim y))
| str-list))
This does not apply a mapping function. Try interleaving a mapping
function INSIDE the LAMBDA and see how your solution looks. (The MAPL
solutions in this thread look better)
Also, The objections against CONCATENATE in this thread were that it is
the least efficient, consing up too many unnecessary strings, doubly so
if you were going to cons up an intermediate LIST to call REDUCE on.
I'd consider this is antithesis of Lisp elegance.
| I seem to recall once reading a ~/.../ solution from Juho Snellman
| about this one. I thought it was nicer than "~~{~~A~~^~A~~}" and-
| replace-the-tildes-if-need-be.
1See my other post in this thread where I have done exactly this.
<··············@moon.robolove.meer.net> In retrospect in MAPCONCAT I
would bind the global after calling MAP.
--
Madhu
On Jul 13, 9:49 pm, Madhu <·······@meer.net> wrote:
> * Kyle M <····································@d34g2000vbm.googlegroups.com> :
> Wrote on Mon, 13 Jul 2009 15:43:43 -0700 (PDT):
>
> | On Jul 10, 4:29 pm, Thierry Pirot
> |> Teemu Likonen> wonder if there is similar function in CL like Emacs Lisp's "mapconcat":
> |>
> |> > (mapconcat 'identity '("one" "two" "three") "-")
> |> > => "one-two-three"
> |>
> |> (defun connect-by-hyphen (x y)
> |> (concatenate 'string x "-" y))
> |>
> |> (reduce #'connect-by-hyphen '("one" "two" "three"))
> |
> |
> | I like your idea the best. More elegant than the nested formats
> | anyway. I would write it this way:
> |
> | (defun mapconcat (str-list delim)
> | (reduce (lambda (x y)
> | (concatenate 'string x delim y))
> | str-list))
>
> This does not apply a mapping function. Try interleaving a mapping
> function INSIDE the LAMBDA and see how your solution looks. (The MAPL
> solutions in this thread look better)
>
OK, that's my mistake. Anyhow, all you really need is the key
argument:
(defun mapconcat (fn list delim)
(reduce (lambda (x y)
(concatenate 'string
x delim y))
list :key fn))
> Also, The objections against CONCATENATE in this thread were that it is
> the least efficient, consing up too many unnecessary strings, doubly so
> if you were going to cons up an intermediate LIST to call REDUCE on.
> I'd consider this is antithesis of Lisp elegance.
>
Oh, come on! This is not the "antithesis of Lisp elegance". It's quick
as hell to write, for starters. I think it's easy to read. It also
works on arrays.
When I wrote that I liked it, I wasn't even thinking about efficiency,
and yet in a couple of quick tests on Allegro CL, it conses less than
your ~/.../ solution. It also conses less than the MAPCON solutions
I've seen around this thread (didn't see any MAPL solutions like you
suggested).
Kyle
* Kyle M <····································@r34g2000vba.googlegroups.com> :
Wrote on Tue, 14 Jul 2009 06:48:23 -0700 (PDT):
|> This does not apply a mapping function. Try interleaving a mapping
|> function INSIDE the LAMBDA and see how your solution looks. (The MAPL
|> solutions in this thread look better)
|
| OK, that's my mistake. Anyhow, all you really need is the key
| argument:
|
| (defun mapconcat (fn list delim)
| (reduce (lambda (x y)
| (concatenate 'string
| x delim y))
| list :key fn))
|
I retract my claim. This fits the bill. Inexplicably I'd forgotten
about the KEY to REDUCE when composing my message, sorry.
|> Also, The objections against CONCATENATE in this thread were that it is
|> the least efficient, consing up too many unnecessary strings, doubly so
|> if you were going to cons up an intermediate LIST to call REDUCE on.
|> I'd consider this is antithesis of Lisp elegance.
|>
|
| Oh, come on! This is not the "antithesis of Lisp elegance". It's quick
| as hell to write, for starters. I think it's easy to read. It also
| works on arrays.
The `antithesis' I wanted to highlight above was in calling, say,
(reduce fN1 (map 'list fN2 SEQ))
| When I wrote that I liked it, I wasn't even thinking about efficiency,
| and yet in a couple of quick tests on Allegro CL, it conses less than
| your ~/.../ solution. It also conses less than the MAPCON solutions
| I've seen around this thread (didn't see any MAPL solutions like you
| suggested).
The FORMAT solution was "elegant", not because it didn't cons, but
because it used FORMAT. OTOH "elegance" with REDUCE would be achieved
by not consing unnecessarily, and by visiting each sequence item exactly
once i.e. the equivalent of doing it all in one loop.
The particular solution I referred to above (which I incorrectly termed
MAPL) was at <···············@luna.vassil.nikolov.name>
--
Madhu
> The FORMAT solution was "elegant", not because it didn't cons, but
> because it used FORMAT. OTOH "elegance" with REDUCE would be achieved
> by not consing unnecessarily, and by visiting each sequence item exactly
> once i.e. the equivalent of doing it all in one loop.
>
The fact that it used FORMAT doesn't make it elegant. The tilde-slash
directive is cool because it makes FORMAT extensible. You get bonus
points for this. However, I say that your FORMAT solution was not
elegant because it required creating a function in a different package
and declaring a variable special. Maybe you do this kind of stuff all
the time, but I'm guessing that you only did it to avoid the
constraints imposed on you by FORMAT.
The FORMAT solutions in this thread are little more than workarounds
for something FORMAT doesn't do easily.
[since you insist]
* Kyle M <····································@r25g2000vbn.googlegroups.com> :
Wrote on Tue, 14 Jul 2009 10:53:10 -0700 (PDT):
|> The FORMAT solution was "elegant", not because it didn't cons, but
|> because it used FORMAT. OTOH "elegance" with REDUCE would be achieved
|> by not consing unnecessarily, and by visiting each sequence item exactly
|> once i.e. the equivalent of doing it all in one loop.
|
| The fact that it used FORMAT doesn't make it elegant.
You have missed the point. The point I was making was you were
comparing apples to oranges when you compared your REDUCE solution with
various FORMAT solutions by measuring CONSING, and presenting the
information. The should be judged using different standards.
Specifically the elegance of the FORMAT solutions are judged on their
merits, which are to be considered given the mechasnism and constraints
in the FORMAT specification. Obviously.
| The tilde-slash directive is cool because it makes FORMAT extensible.
| You get bonus points for this.
You mean the inventors of FORMAT were cool
| However, I say that your FORMAT solution was not elegant because it
| required creating a function in a different package and declaring a
| variable special.
This is the easiest clearest way to solve the problem with the mechanism
provided by the tilde-slash directive. You _have_ to have a global
function in CL-USER because the spec demands it. There are other ways
to implement it (say without a special variable), but this involves new
complexicating "patterns". In this case the simplest clearest way of
using tilde-slash is also most elegant.
| Maybe you do this kind of stuff all the time,
(Not sure what you are referring to)
| but I'm guessing that you only did it to avoid the constraints imposed
| on you by FORMAT.
|
| The FORMAT solutions in this thread are little more than workarounds
| for something FORMAT doesn't do easily.
Actually FORMAT's prime directive is Output, not concatenating strings.
The fact that FORMAT can be used for this problem with essentially a
"O(1)-liner" is what makes using FORMAT "elegant" to solve this problem.
This is the point I was making in the sentence you objected to.
--
Madhu
From: Pascal J. Bourguignon
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <877hyafq4k.fsf@galatea.local>
Madhu <·······@meer.net> writes:
> [since you insist]
>
> * Kyle M <····································@r25g2000vbn.googlegroups.com> :
> Wrote on Tue, 14 Jul 2009 10:53:10 -0700 (PDT):
> | However, I say that your FORMAT solution was not elegant because it
> | required creating a function in a different package and declaring a
> | variable special.
>
> This is the easiest clearest way to solve the problem with the mechanism
> provided by the tilde-slash directive. You _have_ to have a global
> function in CL-USER because the spec demands it.
Actually, this is wrong.
C/USER[411]> (defpackage "F" (:use "CL") (:export "X"))
#<PACKAGE F>
C/USER[412]> (defun F:X (stream object &rest args) (princ "X" stream))
F:X
C/USER[413]> (format t "~/F:X/" 'toto)
X
NIL
C/USER[414]>
--
__Pascal Bourguignon__
Pascal J. Bourguignon <···@informatimago.com> wrote:
+---------------
| Madhu <·······@meer.net> writes:
| > This is the easiest clearest way to solve the problem with the
| > mechanism provided by the tilde-slash directive. You _have_ to
| > have a global function in CL-USER because the spec demands it.
|
| Actually, this is wrong.
|
| C/USER[411]> (defpackage "F" (:use "CL") (:export "X"))
| #<PACKAGE F>
| C/USER[412]> (defun F:X (stream object &rest args) (princ "X" stream))
| F:X
| C/USER[413]> (format t "~/F:X/" 'toto)
| X
| NIL
| C/USER[414]>
+---------------
By the way, have you ever noticed that ~/NAME/ violates the ":"/"::"
reader protocol for "external/internal" symbol indication?
> (defpackage "F" (:use "CL"))
#<The F package, 0/9 internal, 0/2 external>
> (defun F::X (stream object &rest args)
(declare (ignorable object args))
(princ "X" stream))
F::X
> (format t "~/F::X/" 'toto) ; This I expected to work.
X
NIL
> (format t "~/F:X/" 'toto) ; This I didn't.
X
NIL
>
And, no, I didn't accidentally make X external: ;-}
> (find-symbol "X" "F")
F::X
:INTERNAL
> (ignore-errors (read-from-string "F::X"))
F::X
4
> (ignore-errors (read-from-string "F:X")) ; Error expected here.
NIL
#<LISP::READER-PACKAGE-ERROR {48A42615}>
>
Anyway, as odd as this is, the CLHS seems to require it:
22.3.5.4 Tilde Slash: Call Function
...
If NAME contains a single colon (:) or double colon (::), then
everything up to but not including the first ":" or "::" is taken
to be a string that names a package. Everything after the first
":" or "::" (if any) is taken to be a string that names a symbol.
The function corresponding to a ~/NAME/ directive is obtained by
looking up the symbol that has the indicated name in the indicated
package.
...
Notice that the lookup is *not* described in terms of READ of
the whole name, but rather as a FIND-SYMBOL or INTERN of the
pieces of NAME separately. Anybody know why?
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
* (Rob Warnock) <································@speakeasy.net> :
Wrote on Wed, 15 Jul 2009 02:23:31 -0500:
| By the way, have you ever noticed that ~/NAME/ violates the ":"/"::"
| reader protocol for "external/internal" symbol indication?
[...]
| Anyway, as odd as this is, the CLHS seems to require it:
|
| 22.3.5.4 Tilde Slash: Call Function
| ...
| If NAME contains a single colon (:) or double colon (::), then
| everything up to but not including the first ":" or "::" is taken
| to be a string that names a package. Everything after the first
| ":" or "::" (if any) is taken to be a string that names a symbol.
| The function corresponding to a ~/NAME/ directive is obtained by
| looking up the symbol that has the indicated name in the indicated
| package.
| ...
|
| Notice that the lookup is *not* described in terms of READ of the
| whole name, but rather as a FIND-SYMBOL or INTERN of the pieces of
| NAME separately. Anybody know why?
The preceeding 2 sentences of that section impose additional constraints
on NAME:
,----
| NAME can be any arbitrary string that does not contain a "/". All of
| the characters in NAME are treated as if they were upper case.
`----
The `NAME cannot contain a /' restriction would imply the usual reader
algorithm to read in a symbol would not be work, and also indicates how
FORMAT could implement this directive.
--
Madhu
Nice. However, strictly speaking, the FORMAT solution is not a
MAPCONCAT equivalent.
It does not map the list but simply concatenates the items together.
> Try:
>
> (time (let ((*print-pretty* nil)) (format nil "~{~a~^-~}" *mylist*)))
>
> It takes about 0.002 seconds for me.
>
> Zach
jgrant <········@gmail.com> writes:
> Nice. However, strictly speaking, the FORMAT solution is not a
> MAPCONCAT equivalent.
> It does not map the list but simply concatenates the items together.
Yeah, but that's trivial:
(defun mapconcat (function list elem)
(let (*print-pretty*)
(format nil (format nil "~~{~~a~~^~a~~}" elem)
(mapcar function list))))
When run with your *mylist* code this takes .004 seconds vs. .096 for
your version.
But I don't know if your solution could be tightened up...it _should_ be
possible to beat the performance of FORMAT for this one way or another.
Lesson here: *pretty-print* is _expensive_.
--
Robert Uhl <http://public.xdi.org/=ruhl>
If infinite rednecks fired infinite shotguns at an infinite number of road
signs, they'd eventually create all the great literary works of the world in
braille. --Discordian Quote File
> But I don't know if your solution could be tightened up...it _should_ be
> possible to beat the performance of FORMAT for this one way or another.
With a few trivial changes it matches the FORMAT version very
closely :
(defun mapconcat(func lst sep)
(declare (type (cons (simple-array character (*))) lst))
(declare (type (simple-array character (*)) sep))
(let ((vs (make-array 0
:element-type 'character
:fill-pointer 0
:adjustable t))
(lsep (length sep)))
(mapcar #'(lambda (str)
(let ((nstr (funcall func str)))
(declare (type (simple-array character (*)) str))
(dotimes (j (length str) j)
(declare (type fixnum j))
(vector-push-extend (char str j) vs))
(dotimes (k lsep k)
(declare (type fixnum k))
(vector-push-extend (char sep k) vs))))
lst)
vs))
* (time (mapconcat 'identity *mylist* "-"))
Evaluation took:
0.005 seconds of real time
0.005106 seconds of total run time (0.005080 user, 0.000026 system)
100.00% CPU
11,783,457 processor cycles
605,248 bytes consed
The lesson for this version is that the performance of NTH sucks, use
MAPCAR instead.
From: Pascal J. Bourguignon
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <877hyfjal4.fsf@galatea.local>
Robert Uhl <·········@NOSPAMgmail.com> writes:
> jgrant <········@gmail.com> writes:
>
>> Nice. However, strictly speaking, the FORMAT solution is not a
>> MAPCONCAT equivalent.
>> It does not map the list but simply concatenates the items together.
>
> Yeah, but that's trivial:
>
> (defun mapconcat (function list elem)
> (let (*print-pretty*)
> (format nil (format nil "~~{~~a~~^~a~~}" elem)
> (mapcar function list))))
>
> When run with your *mylist* code this takes .004 seconds vs. .096 for
> your version.
>
> But I don't know if your solution could be tightened up...it _should_ be
> possible to beat the performance of FORMAT for this one way or another.
>
> Lesson here: *pretty-print* is _expensive_.
Unfortunately, this doesn't work if elem contains a tilde.
See my solution.
--
__Pascal Bourguignon__
* (Pascal J. Bourguignon) <··············@galatea.local> :
Wrote on Sat, 11 Jul 2009 21:14:47 +0200:
| Robert Uhl <·········@NOSPAMgmail.com> writes:
|
|> (defun mapconcat (function list elem)
|> (let (*print-pretty*)
|> (format nil (format nil "~~{~~a~~^~a~~}" elem)
|> (mapcar function list))))
|>
| Unfortunately, this doesn't work if elem contains a tilde.
| See my solution.
You can still use FORMAT elegantly[1] without escaping the tildaes:
(defun cl-user::mapconcat-aux (stream &rest args)
(declare (ignore args) (special *sep*))
(write-string *sep* stream))
(defun mapconcat (function sequence separator)
(let ((*sep* separator))
(declare (special *sep*))
(format nil "~{~A~^~:*~/mapconcat-aux/~}"
(map 'list function sequence))))
--
Madhu
[1] but still falls short of elegance standards in
<·······················@cleycom>
From: Giorgos Keramidas
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <87vdlybimu.fsf@kobe.laptop>
On Sat, 11 Jul 2009 12:50:10 -0600, Robert Uhl <·········@NOSPAMgmail.com> wrote:
> jgrant <········@gmail.com> writes:
>
>> Nice. However, strictly speaking, the FORMAT solution is not a
>> MAPCONCAT equivalent.
>> It does not map the list but simply concatenates the items together.
>
> Yeah, but that's trivial:
>
> (defun mapconcat (function list elem)
> (let (*print-pretty*)
> (format nil (format nil "~~{~~a~~^~a~~}" elem)
> (mapcar function list))))
>
> When run with your *mylist* code this takes .004 seconds vs. .096 for
> your version.
>
> But I don't know if your solution could be tightened up...it _should_ be
> possible to beat the performance of FORMAT for this one way or another.
>
> Lesson here: *pretty-print* is _expensive_.
A version that doesn't use format may be something like this:
CL-USER> (defun mapconcat (function sequence separator)
(with-output-to-string (*standard-output*)
(mapcon (lambda (seq)
(princ (funcall function (first seq)))
(when (cdr seq)
(princ separator)))
sequence)))
MAPCONCAT
It's slightly faster than the format version, and a bit less 'cryptic'
for those who feel uncomfortable with long-winded formatting strings:
CL-USER> (defun mapconcat-format (function list elem)
(let ((*print-pretty*))
(format nil (format nil "~~{~~a~~^~a~~}" elem)
(mapcar function list))))
MAPCONCAT-FORMAT
CL-USER> (defparameter *numbers* (loop for x below (expt 10 6) collect x))
*NUMBERS*
CL-USER> (time (prog1 nil
(mapconcat-format #'evenp *numbers* "-")))
Evaluation took:
1.593 seconds of real time
1.587026 seconds of total run time (1.421907 user, 0.165119 system)
[ Run times consist of 0.533 seconds GC time, and 1.055 seconds non-GC
time. ]
99.62% CPU
2,860,040,520 processor cycles
36,507,520 bytes consed
NIL
CL-USER> (time (prog1 nil
(mapconcat #'evenp *numbers* "-")))
Evaluation took:
1.255 seconds of real time
1.250247 seconds of total run time (1.197851 user, 0.052396 system)
[ Run times consist of 0.003 seconds GC time, and 1.248 seconds non-GC
time. ]
99.60% CPU
2,252,216,232 processor cycles
28,502,648 bytes consed
NIL
Both versions have the same bug, though. They work only for lists, so
they have to be tweaked to work with vectors and strings too. Doing
that without coercing everything to a list should be amusing :-)
Giorgos Keramidas <········@ceid.upatras.gr> writes:
>
> A version that doesn't use format may be something like this:
>
> CL-USER> (defun mapconcat (function sequence separator)
> (with-output-to-string (*standard-output*)
> (mapcon (lambda (seq)
> (princ (funcall function (first seq)))
> (when (cdr seq)
> (princ separator)))
> sequence)))
> MAPCONCAT
>
> It's slightly faster than the format version, and a bit less 'cryptic'
> for those who feel uncomfortable with long-winded formatting strings:
Bravo! Faster and clearer too.
--
Robert Uhl <http://public.xdi.org/=ruhl>
I have an asteroid named after me. Isaac Asimov's got one too.
It's smaller and more eccentric. --Arthur C. Clarke
> > It's slightly faster than the format version, and a bit less 'cryptic'
> > for those who feel uncomfortable with long-winded formatting strings:
>
> Bravo! Faster and clearer too.
>
Your version is slower(by a factor of about 1100X, uses 60X more
memory) than the FORMAT version and the version that I posted
previously.
Your version :
* (time (mapconcat 'identity *mylist* "-"))
Evaluation took:
5.564 seconds of real time
5.503842 seconds of total run time (5.478909 user, 0.024933 system)
[ Run times consist of 0.008 seconds GC time, and 5.496 seconds non-
GC time. ]
98.92% CPU
12,541,595,156 processor cycles
35,011,632 bytes consed
Zach's FORMAT version :
* (time (mapconcat 'identity *mylist* "-"))
Evaluation took:
0.004 seconds of real time
0.004074 seconds of total run time (0.004074 user, 0.000000 system)
100.00% CPU
9,184,344 processor cycles
538,432 bytes consed
Mine :
* (time (mapconcat 'identity *mylist* "-"))
Evaluation took:
0.005 seconds of real time
0.004695 seconds of total run time (0.004694 user, 0.000001 system)
100.00% CPU
10,580,341 processor cycles
606,304 bytes consed
From: Pascal J. Bourguignon
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <87fxd1ibm9.fsf@galatea.local>
Robert Uhl <·········@NOSPAMgmail.com> writes:
> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>>
>> A version that doesn't use format may be something like this:
>>
>> CL-USER> (defun mapconcat (function sequence separator)
>> (with-output-to-string (*standard-output*)
>> (mapcon (lambda (seq)
>> (princ (funcall function (first seq)))
>> (when (cdr seq)
>> (princ separator)))
>> sequence)))
>> MAPCONCAT
>>
>> It's slightly faster than the format version, and a bit less 'cryptic'
>> for those who feel uncomfortable with long-winded formatting strings:
>
> Bravo! Faster and clearer too.
MAPL was wanted instead of MAPCON.
What's the point of consing a list to be throw away immediately?
But either MAPCON or MAPL would work only on lists, so it would be
clearer to s/sequence/list/, or to change that for:
(etypecase sequence
(list
(when sequence
(princ (funcall function (first sequence)))
(dolist (item (rest sequence))
(princ separator)
(princ (funcall function item)))))
(vector
(when (plusp (length sequence))
(princ (funcall function (aref sequence 0)))
(loop
:for i :from 1 :below (length sequence)
:do (princ separator)
(princ (funcall function (aref sequence i)))))))
There's also a way to cut in half the processing time of
with-output-to-string: by computing the total length before copying
data there. Unfortunately, for that we have to cons an intermediary
sequence, so if there are a lot of small strings, it may not be more
efficient.
(defun mapconcat (function sequence separator)
(etypecase sequence
(list
(if sequence
(let* ((items (mapcar (lambda (item)
(let ((sitem (funcall function item)))
(if (stringp sitem)
sitem
(princ-to-string sitem))))
sequence))
(ssepa (if (stringp separator)
separator
(princ-to-string separator)))
(size (+ (reduce (function +) items :key (function length))
(* (length ssepa) (1- (length items)))))
(result (make-array size :element-type 'character))
(start 0))
(replace result (first items) :start1 start)
(incf start (length (first items)))
(dolist (item (rest items))
(replace result ssepa :start1 start) (incf start (length ssepa))
(replace result item :start1 start) (incf start (length item)))
result)
""))
(vector
(if (plusp (length sequence))
(let* ((items (map 'vector (lambda (item)
(let ((sitem (funcall function item)))
(if (stringp sitem)
sitem
(princ-to-string sitem))))
sequence))
(ssepa (if (stringp separator)
separator
(princ-to-string separator)))
(size (+ (reduce (function +) items :key (function length))
(* (length ssepa) (1- (length items)))))
(result (make-array size :element-type 'character))
(start 0))
(replace result (aref items 0) :start1 start) (incf start (length (aref items 0)))
(loop
:for i :from 1 :below (length items)
:do (replace result ssepa :start1 start) (incf start (length ssepa))
(replace result (aref items i) :start1 start) (incf start (length (aref items i))))
result)
""))))
(values (mapconcat (function 1+) '(1 2 3 4) '-)
(mapconcat (function 1+) #(1 2 3 4) '-))
--> "2-3-4-5" ;
"2-3-4-5"
--
__Pascal Bourguignon__
On Mon, 13 Jul 2009 04:02:22 +0200, ···@informatimago.com (Pascal J. Bourguignon) said:
> ...
> But either MAPCON or MAPL would work only on lists,
Indeed. This is a significant point.
> so it would be clearer to s/sequence/list/, or to change that for:
> (etypecase sequence
> ...)
I would do it thus, rather than dispatch by hand (especially that
VECTOR and LIST "are not necessarily an exhaustive partition of
sequence", according to the description of the system class
SEQUENCE):
(defun mapconcat (f xs s)
"Map F on XS and concatenate the results into a string, S-separated.
Similar to Elisp's `mapconcat'. \"Demo\" grade."
(with-output-to-string (result)
(let ((s-p nil))
(map nil
#'(lambda (x)
(if s-p (princ s result) (setq s-p t))
(princ (funcall f x) result))
xs))))
> ...
> There's also a way to cut in half the processing time of
> with-output-to-string: by computing the total length before copying
> data there. Unfortunately, for that we have to cons an intermediary
> sequence, so if there are a lot of small strings, it may not be more
> efficient.
Indeed; I would do it thus, however, which I believe is simpler:
(defun mapconcat (f xs s)
"Map F on XS and concatenate the results into a string, S-separated.
Similar to Elisp's `mapconcat'; F is assumed to return strings,
and S is assumed to be a string. \"Demo\" grade."
(let* ((ys (map 'list f xs))
(s-size (if (endp ys) 0 (* (1- (length ys)) (length s))))
(size (+ s-size (reduce #'+ ys :key #'length)))
(result (make-array size :fill-pointer 0 :element-type 'character)))
(with-output-to-string (result result)
(let ((s-p nil))
(map nil
#'(lambda (y)
(if s-p (princ s result) (setq s-p t))
(princ y result))
ys)))
result))
So, for example,
(mapconcat #'string "foo" "-") => "f-o-o"
---Vassil.
--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
Correction:
On Mon, 13 Jul 2009 00:37:55 -0400, Vassil Nikolov <········@pobox.com> said:
> ...
> (defun mapconcat (f xs s)
> "Map F on XS and concatenate the results into a string, S-separated.
> Similar to Elisp's `mapconcat'; F is assumed to return strings,
> and S is assumed to be a string. \"Demo\" grade."
> (let* ((ys (map 'list f xs))
> (s-size (if (endp ys) 0 (* (1- (length ys)) (length s))))
> (size (+ s-size (reduce #'+ ys :key #'length)))
> (result (make-array size :fill-pointer 0 :element-type 'character)))
> (with-output-to-string (result result)
> (let ((s-p nil))
> (map nil
> #'(lambda (y)
> (if s-p (princ s result) (setq s-p t))
^^^^^ this should be write-string, of course
> (princ y result))
^^^^^ ditto
> ys)))
> result))
---Vassil.
--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Giorgos Keramidas
Subject: Re: Emacs Lisp's "mapconcat" in Common Lisp?
Date:
Message-ID: <878wisepps.fsf@kobe.laptop>
On Mon, 13 Jul 2009 04:02:22 +0200, ···@informatimago.com (Pascal J. Bourguignon) wrote:
> Giorgos Keramidas <········@ceid.upatras.gr> writes:
>>
>> A version that doesn't use format may be something like this:
>>
>> CL-USER> (defun mapconcat (function sequence separator)
>> (with-output-to-string (*standard-output*)
>> (mapcon (lambda (seq)
>> (princ (funcall function (first seq)))
>> (when (cdr seq)
>> (princ separator)))
>> sequence)))
>> MAPCONCAT
>>
>> It's slightly faster than the format version, and a bit less 'cryptic'
>> for those who feel uncomfortable with long-winded formatting strings:
>
> MAPL was wanted instead of MAPCON.
> What's the point of consing a list to be throw away immediately?
Very good point, thanks! I am not familiar with _all_ the mapping
functions yet :)
jgrant <········@gmail.com> writes:
> Nice. However, strictly speaking, the FORMAT solution is not a
> MAPCONCAT equivalent.
> It does not map the list but simply concatenates the items together.
I don't really care about that. People don't always consider
*PRINT-PRETTY* when benchmarking FORMAT. Most of the time, using a
*PRINT-PRETTY* value of NIL will make FORMAT much faster.
Zach
On Jul 11, 11:01 am, Zach Beane <····@xach.com> wrote:
> > It does not map the list but simply concatenates the items together.
>
> I don't really care about that. People don't always consider
> *PRINT-PRETTY* when benchmarking FORMAT. Most of the time, using a
> *PRINT-PRETTY* value of NIL will make FORMAT much faster.
>
Sure, it's worth noting the performance of *PRETTY-PRINT* but the
topic was about a MAPCONCAT implementation.
My point was to demonstrate how something like that would be
implemented. The FORMAT version works just great and is useful for
pointing out the incredible power of FORMAT directives but it doesn't
demonstrate a lower-level implementation in CL.
------------------------
http://jng.imagine27.com
jgrant <········@gmail.com> writes:
> On Jul 11, 11:01 am, Zach Beane <····@xach.com> wrote:
>> > It does not map the list but simply concatenates the items together.
>>
>> I don't really care about that. People don't always consider
>> *PRINT-PRETTY* when benchmarking FORMAT. Most of the time, using a
>> *PRINT-PRETTY* value of NIL will make FORMAT much faster.
>>
>
> Sure, it's worth noting the performance of *PRETTY-PRINT* but the
> topic was about a MAPCONCAT implementation.
> My point was to demonstrate how something like that would be
> implemented. The FORMAT version works just great and is useful for
> pointing out the incredible power of FORMAT directives but it doesn't
> demonstrate a lower-level implementation in CL.
I responded because you included TIME output showing how slow FORMAT is
compared to something else. It need not be so slow.
Zach
On 2009-07-10 16:38:01 +0100, Teemu Likonen <········@iki.fi> said:
> But I have a feeling that there could be a more elegant way. Is there?
Elegance, in CL, is generally judged by how much of your code you can
write using either FORMAT or the more obscure features of LOOP. Some
also consider complicated backquoted expressions to count, but they do
not score unless you have chains of at least 4 comma/quote/at-signs.
Using tail recursion counts as negative 5.