4
\$\begingroup\$

I needed to have a Lisp function that could produce a string of a certain length, created by repeated concatenations of a another string given as argument (so for example by giving 10 and "abc" I could obtain "abcabcabca"). I came up with a perverse idea of using a circular list of characters in combination with the loop macro. I'm not really aiming at great performance, but I'm wondering what are the disadvantages of this approach and what could be improved. I also added a switch indicating at which end to start filling the string.

(defun pad-with-string (n str &key (from-end nil))
  "Create a string of length `n` filled with repeating instances of `str`.
If `from-end` is T the string is filled from the end."
  (labels ((circular-list (&rest elements)
         (let ((cycle (copy-list elements)))
           (nconc cycle cycle))))
    (loop :repeat n 
       :for c 
       :in (apply #'circular-list (coerce (if from-end (nreverse str) str) 'list)) 
       :collect c 
       :into chars
       :finally (return (coerce (if from-end (nreverse chars) chars) 'string)))))
\$\endgroup\$
3
\$\begingroup\$

Not a bad approach.

I can see one arguable bug, and have a few style notes on your code though. Lets start with the bug:

CL-USER> (defparameter a "test")
A
CL-USER> (pad-with-string 6 a :from-end t)
"tsetts"
CL-USER> a
"tset"
CL-USER> 

Is that what you were expecting? It's happening because you call nreverse on your input argument if from-end is passed. When I've got a situation where I have to mutate parameters, I follow the Scheme convention and name the procedure with a trailing bang (so, like pad-with-string!). Your comments state that you don't care about efficiency though, which leads me to believe you could just use the standard reverse rather than nreverse.


You're using apply on circular list, but you're defining it locally and only calling it in one place. In this situation, I'd kill the &rest and just call the function

...
  (labels ((circular-list (elements)
         (let ((cycle (copy-list elements)))
           (nconc cycle cycle))))
    (loop :repeat n 
       :for c 
       :in (circular-list (coerce (if from-end (nreverse str) str) 'list)) 
...

You've got the (if from-end (reverse a) a) pattern in a couple of places. I'd pull that out into an additional local definition.

...
       (maybe-reverse (thing) 
         (if from-end (reverse thing) thing)))
    (loop :repeat n 
       :for c
       :in (circular-list (coerce (maybe-reverse str) 'list)) 
       :collect c
       :into chars
       :finally (return (coerce (maybe-reverse chars) 'string)))))

thanks to Rainer for pointing this out

The result of the collect call is returned implicitly at the end of the loop unless you give it an explicit name. Which means you can avoid finally (return ...) by wrapping those transformations around the loop itself:

...
(coerce 
 (maybe-reverse
  (loop :repeat n 
     :for c
     :in (circular-list (coerce (maybe-reverse str) 'list)) 
     :collect c))
 'string)))

Not a hard and fast rule, but people typically use symbols rather than keywords for loop words. So,

...
(coerce 
 (maybe-reverse
  (loop repeat n 
     for c
     in (circular-list (coerce (maybe-reverse str) 'list)) 
     collect c))
 'string)))

Again, there's not really a standard for this, but I tend to like putting conditions and their effects/modifiers on the same line.

...
(coerce 
 (maybe-reverse
  (loop repeat n 
     for c in (circular-list (coerce (maybe-reverse str) 'list)) 
     collect c))
 'string)))

So,

(defun pad-with-string (n str &key (from-end nil))
  (labels ((circular-list (elements)
             (let ((cycle (copy-list elements)))
               (nconc cycle cycle)))
           (maybe-reverse (thing) 
             (if from-end (reverse thing) thing)))
    (coerce (maybe-reverse
              (loop repeat n
                 for c in (circular-list (coerce (maybe-reverse str) 'list))
                 collect c))
            'string)))
\$\endgroup\$
  • \$\begingroup\$ Thanks for the extensive answer, @Inaimathi. I totally missed the possible consequences of using nreverse. I used keywords in the loop macro, because my SLIME completes those but not symbols. \$\endgroup\$ – Wojciech Gac Apr 30 '14 at 21:34
  • \$\begingroup\$ As for circular-list, it was meant to have syntax analogous to list (I took the code from Quickutils), but I agree that with a local definition it would be more natural not to have to use apply. \$\endgroup\$ – Wojciech Gac May 1 '14 at 8:26
  • 1
    \$\begingroup\$ Great answer. Personally I would also get rid of the FINALLY (RETURN ...) part and wrap the (coerce (maybe-reverse ...)) call around the LOOP. That would seem to me slightly more Lisp-like. \$\endgroup\$ – Rainer Joswig May 3 '14 at 16:33
3
\$\begingroup\$

Say, if you only wanted to ever pad with the whole given string and not fractions of it, something like this would do the job:

(format nil "~v@{~A~:*~}" 3 "abc")

The above produces: "abcabcabc"

Which you could then subseq if you wanted to have only a fraction of a string.

Meaning of the directives used in the format:

  • ~v allows substitution of a numerical argument for directives that can take a numeric argument.
  • ~@{ beginning of iteration, @ modifier tells that arguments are taken as if they were inside a list.
  • ~A prints the Lisp object such that it would look "pretty", but not necessary readable by the Lisp reader.
  • ~:* instructs the format processor to move to the first argument of the list it was iterating over (in our case there's only one argument).
  • ~} terminates iteration.

Generally speaking. It's best to avoid coercing strings to lists when generating string, unless it's a constant length small string. It's best to use printing and with-output-to-string, as this is usually efficiently handled by the Lisp system.

And a trivial solution for this would look something like this:

(defun padded-string (padding n &optional from-end)
  (with-output-to-string (s)
    (loop :for i :below n
       :with padding := (if from-end (reverse padding) padding)
       :do (princ (char padding (mod i (length padding))) s))))

The optimized version:

(defun pad-string-optimized (padding n &optional from-end)
  (declare (optimize speed)
           (type string padding))
  (loop :with result := (make-string n :initial-element #\x)
     :and padding := (if from-end (reverse padding) padding)
     :and len := (length padding)
     :for i fixnum :below n
     :do (setf (aref result i) (aref padding (mod i len)))
     :finally (return result)))

Seems to be about 5 times faster than any of the above, and is a lot less demanding in terms of memory usage.

\$\endgroup\$
  • \$\begingroup\$ Hm. I'm not seeing it in practice. I just tried to run this function and the one from above using coerce through the SLIME profiler and got measuring PROFILE overhead..done seconds | gc | consed | calls | sec/call | name ---------------------------------------------------------- 8.454 | 0.064 | 374,104,320 | 40,000 | 0.000211 | PADDED-STRING 1.046 | 0.084 | 537,730,656 | 40,000 | 0.000026 | PAD-WITH-STRING ---------------------------------------------------------- 9.499 | 0.148 | 911,834,976 | 80,000 | | Total \$\endgroup\$ – Inaimathi Jan 5 '15 at 20:50
  • \$\begingroup\$ (ctd.) Is that a statistical artifact, does SBCL optimize coercions in some way, or something else? \$\endgroup\$ – Inaimathi Jan 5 '15 at 20:52
  • \$\begingroup\$ @Inaimathi you are not comparing the right thing... First of all, you need to tell the compiler to optimize your code, if you are interested in the code that runs fast. Next, my code uses an order of magnitude less memory, so depending on what system you will run it it may or may not affect the performance. Anyway, pastebin.com/ra4Te3Hq I tried to optimize both functions a bit, but pad-with-string is more difficult to optimize too. \$\endgroup\$ – wvxvw Jan 5 '15 at 21:32
  • 2
    \$\begingroup\$ On the same note, if you were really after performance, you would simply calculate the length of the string beforehand, and write the pattern into this string as many times as needed. I simply think that my code is less convoluted and just shorter. \$\endgroup\$ – wvxvw Jan 5 '15 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.