0

Q: how do I rotate the elements of a list such that last becomes first?

Given a list of arbitrary length, how do I rotate the list non-destructively such that the last element becomes the first element?

What doesn't work

cl-rotatef doesn't seem to work for my purposes. First, it modifies in place (but I could deal with that). Second, it spits up when I use butlast and last (apparently, they're not setf-able):

(let ((list '(a b c)))
  (cl-rotatef (butlast list) (last list)))

gives the error message

Symbol's function definition is void: (setf butlast)

What works, but seems inefficient

Here's what I've got:

(let ((list '(a b c)))
  (let ((rev (reverse list)))
    (cons (pop rev) (nreverse rev))))    ; => (c a b)

This snippet works as expected. However, it seems inefficient in that it reverses at the front and then nreverses at the back.

I'm only using this function on short lists (3 or 4 elements at most), so it's not such a big deal in practice. But I'd still like to know how to rotate efficiently. (If there's a built-in function to do this that I've missed, even better.)

  • 1
    Your "inefficient" version is already quasi optimal in the number of memory allocations, and in terms of CPU the extra cost of nreverse should be largely negligible (nreverse is a constant factor faster than reverse). If you want to get rid of the extra allocation, just use something like (progn (cl-callf nreverse (cdr rev)) rev) – Stefan Oct 30 '17 at 13:02
  • I recall reading one or two functions in Magnar's libraries that rotate, but I'm not sure if that is what you are looking for. I copied a few of them over to my personal config just in case I ever need them: !cdr, !cons, dotimes, take, rotate, nreverse-nondesctructive, ... I probably modified by combining and renaming some of them ... – lawlist Nov 1 '17 at 1:51
2

Edit: Oh, I misread your rotating direction.

(setq more-tree '(maple birch pine oak))              ; => (maple birch pine oak)
(nconc (last more-tree) (butlast more-tree))          ; => (oak maple birch pine)

The most basic built-in tools for that are car and cdr. The former giving you the first element f the list, the latter the rest of the list. Two functions append to a list: append and nconc, both would want a list as the append value, which I create with (cons 'value ())

(setq more-tree '(maple birch pine oak))              ; => (maple birch pine oak)

(append (cdr more-tree) (cons (car more-tree) ()))    ; => (birch pine oak maple)
;; or
(nconc (cdr more-tree) (cons (car more-tree) ()))     ; => (birch pine oak maple)
0

A "hardcore" version, that only looks at each element once:

(defun rotate-list (original)
  (when original
    (let ((last (list (car original)))
          (original (cdr original)))
      (if original
          (let* ((acc (list (car original)))
                 (acc-tail acc))
            (while (setq original (cdr original))
              (rplacd acc-tail (list (car original)))
              (setq acc-tail (cdr acc-tail)))
            (rplacd acc-tail last)
            acc)
        last))))

On a related note: list data structure isn't a perfect candidate for this kind of operation. If this is a one-of event where you need to do this, it's fine, but if this is something that will be reused often, then, perhaps you should consider using vectors, where this is easier to implement and runs faster.

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.