How to rotate a list that goes in the right direction

Question

I want to be able to make my list go one step to the right. Here's my example code that makes it go one step to the left. (define (rotate-L lst) (append (cdr lst) (list (car lst)))) (rotate-L '(a b c))

(b c a)

I'm having trouble understanding why when I make it backward, i get an error (define (rotate-L lst) (append (car lst) (list (cdr lst)))) (rotate-L '(a b c)) SchemeError: argument 0 of append has wrong type (string)

Current Eval Stack:

0: (rotate-L (quote (a b c)))

Answer 1

(define rotr
  (lambda (l)
    (if (null? l)
        l
        ((lambda (s) (s s l cons))
         (lambda (s l c)
           (if (null? (cdr l))
               (c (car l) '())
               (s s (cdr l)
                  (lambda (f r)
                    (c f (cons (car l) r))))))))))

(define rotl
  (lambda (l0)
    (if (null? l0)
        l0
        ((lambda (s) (s s (cdr l0) (lambda (r) r)))
         (lambda (s l c)
           (if (null? l)
               (c (list (car l0)))
               (s s (cdr l)
                  (lambda (r)
                    (c (cons (car l) r))))))))))

Here is a test:

(rotr '())
(rotr '(a))
(rotr '(a b))
(rotr '(a b c))
(rotl '())
(rotl '(a))
(rotl '(a b))
(rotl '(a b c))

whose output is so:

1 ]=> (rotr '())
;Value: ()

1 ]=> (rotr '(a))
;Value: (a)

1 ]=> (rotr '(a b))
;Value: (b a)

1 ]=> (rotr '(a b c))
;Value: (c a b)

1 ]=> (rotl '())
;Value: ()

1 ]=> (rotl '(a))
;Value: (a)

1 ]=> (rotl '(a b))
;Value: (b a)

1 ]=> (rotl '(a b c))
;Value: (b c a)

Answer 2

It's worth remembering what lists look like as structures made of conses: (1 2 3 4) looks like this, for instance

So pretty obviously (car '(1 2 3 4)) is a number, not a list, and so (append (car '(1 2 3 4)) ...) is not going to work, because append wants its arguments to be lists. But even if you fix this to be correct, you're not doing what you think:

(define (not-rotating lst)
  (append (list (car lst)) (cdr lst)))

This simply takes the first element of the list, makes a single-element list from it, and appends the rest of the list to it. Well, you could write this more easily:

(define (not-rotating lst)
  (cons (car lst) (cdr list)))

and it should be clear that this is doing nothing at all useful.

To rotate the list 'right' you need to:

• find the last element of the list;
• construct a list which is all of the original list except for that element;
• and glue the last element onto the start of that list.

The only way to find the last element of the list is to walk along the list until you get to it. And you also need to make a copy of all the elements of the list but the last one, which also means walking down the list. It is natural to do these two operations at the same time:

• walk down the list, building up a copy of it;
• when you get to the last element, attach it to the start of the copy.

Here is a terrible way of doing this:

(define (rotate-r/terrible lst)
  (let rrl ((tail lst)
            (building '()))
    (if (null? (cdr tail))
        ;; we've got to the end
        (cons (car tail) building)
        (rrl (cdr tail)
             (append building (list (car tail)))))))

This is terrible because at each step it appends the current element to the end of the list it is building. That's terrible for not one but two reasons:

• appending two lists takes time proportional to the length of the first list;
• appending two lists requires a complete copy of the first list to be made. That makes this both quadratic in the length of the list, which is terrible, and also very 'consy' – it allocates lots of ephemeral storage. But it does work.

So: there is, not surprisingly a better way of doing this: a way which is both linear and makes no more than two copies of the list. I'm not going to give it here, but it's surprisingly close to the above terrible solution. Two hints:

• what is the natural way to accumulate elements into a list? is it at the start, or at the end of a list?
• how do you turn the list you accumulated like that into the list you want?