如何在Scheme中实现列表右旋转？若此为左旋转方法，右旋转该怎么做？

Hey there! Let's walk through how to implement both left and right rotations for lists in Scheme. First, let's align on what these rotations actually do:

• Left rotation by k positions: Grab the first k elements of the list and move them to the end. For example, left-rotating (1 2 3 4 5) by 2 gives (3 4 5 1 2).
• Right rotation by k positions: Take the last k elements of the list and move them to the front. For example, right-rotating (1 2 3 4 5) by 2 gives (4 5 1 2 3).

Implementing Left Rotation #

First up: left rotation. We need to handle edge cases upfront—if k is 0, or k is a multiple of the list's length, the list stays exactly the same. Also, if k is larger than the list length, we use modulo to get the effective rotation amount (since rotating a list of length n by n positions is identical to rotating by 0).

If your Scheme implementation (like Racket) includes the split-at function, this is straightforward:

(define (left-rotate lst k)
  (if (null? lst)
      '()
      (let* ((len (length lst))
             (effective-k (modulo k len)))
        (if (zero? effective-k)
            lst
            (let-values (((front back) (split-at lst effective-k)))
              (append back front))))))

If you're using a standard Scheme without split-at, you can roll your own simple helper to split the list:

(define (split lst n)
  (if (or (zero? n) (null? lst))
      (cons '() lst)
      (let ((split-rest (split (cdr lst) (- n 1))))
        (cons (cons (car lst) (car split-rest)) (cdr split-rest)))))

(define (left-rotate lst k)
  (if (null? lst)
      '()
      (let* ((len (length lst))
             (effective-k (modulo k len)))
        (if (zero? effective-k)
            lst
            (let ((split-pair (split lst effective-k)))
              (append (cdr split-pair) (car split-pair)))))))

Example usage:

(left-rotate '(1 2 3 4 5) 2)  ; Returns (3 4 5 1 2)
(left-rotate '(a b c) 4)       ; Returns (b c a) (since 4 mod 3 = 1)

Implementing Right Rotation #

Right rotation is essentially the inverse of left rotation. Instead of moving the first k elements to the end, we move the last k elements to the front. A clever shortcut is to convert it to a left rotation: rotating right by k positions is the same as rotating left by (length lst - k) positions (we still use modulo to handle edge cases like k being larger than the list length).

Here's the implementation using our existing left rotation function:

(define (right-rotate lst k)
  (if (null? lst)
      '()
      (let* ((len (length lst))
             (effective-k (modulo k len)))
        (left-rotate lst (- len effective-k)))))

Alternatively, you can implement it directly by splitting the list at (- len effective-k) and swapping the two parts:

(define (right-rotate lst k)
  (if (null? lst)
      '()
      (let* ((len (length lst))
             (effective-k (modulo k len))
             (split-point (- len effective-k)))
        (if (zero? effective-k)
            lst
            (let-values (((front back) (split-at lst split-point)))
              (append back front))))))

Example usage:

(right-rotate '(1 2 3 4 5) 2)  ; Returns (4 5 1 2 3)
(right-rotate '(x y z) 1)       ; Returns (z x y)
(right-rotate '(a b c d) 5)     ; Returns (d a b c) (since 5 mod 4 = 1, len -1 =3; left rotate by 3 gives the same result)

Quick Tips #

• Always handle empty lists first to avoid errors when calculating the list length.
• Using modulo also takes care of negative k values: for example, (right-rotate lst -2) is the same as (left-rotate lst 2).

内容的提问来源于stack exchange，提问作者Carla Patania