Re: Emacs Lisp's "mapconcat" in Common Lisp?


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?"
.

Relevant Pages

  • Re: understanding the definiton of limits
    ... the sequence represent its heads (so it has many heads, ... What remains after removing a head is a tail. ... How do we catch such a snake in its nest? ... traps are the most important ones. ...
    (sci.math)
  • Re: a problem with functions of binomials.
    ... the left tail of the Binomial can be expressed as the left ... can define a sequence of n terms ... generic realization H) for which the corresponding probability ... value t has first derivative equal to zero and positive second ...
    (sci.stat.math)
  • Re: Request for Review of ZF Inconsistency Proof
    ... denote the infinite set of denumerable binary strings with alphabet ... sequence of 0s and 1s (or alternatively, ... "tail of zeros"), via reverse binary notation. ...
    (sci.logic)
  • Re: An easy one for you analysts?
    ... be a sequence of positive numbers. ... hence for some tail, all terms are less than 1. ... Correction to the correction: ...
    (sci.math)