Сдвиг k раз влево

Question

Привет. Я пытаюсь реализовать программу в схеме, сдвигая список k раз влево. Например:

(shift-k-left ’(1 2 3) 2)
’(3 1 2)

Мне удалось реализовать код, сдвигающий влево здесь:

(define shift-left
 (lambda (ls)
   (if (null? ls)
    '()
     (append (cdr ls)
          (cons (car ls)
                '())))))

Я хочу использовать сдвиг влево как функцию для shift-k-left.

Answer 1

Использование shift-left для сдвига k раз:

• Если k равно 0: ничего не делать
• Если k не равно 0: сдвиг k-1 раз, а затем shift-left результат.

То есть

(define (shift-left-k ls k)
    (if (= k 0)
        ls
        (shift-left (shift-left-k ls (- k 1)))))

Возможно, вы захотите настроить что-нибудь разумное для отрицательного k.

Answer 2

Идея заключается в обратном отсчете n при cons с car с r до p и cdr с до r, тогда базовый случай становится добавлением r к обратная сторона p. Если мы столкнемся с null? r, мы reverse p и продолжим вращение:

(define (shift-k-left l n)
  ; assume that n >= 0
  (let loop ((n n) (p '()) (r l))   
    (if (= n 0)
        (append r (reverse p))
        (if (null? r)
            (loop n '() (reverse p))
            (loop (- n 1) (cons (car r) p) (cdr r))))))

Answer 3

Вот решение с использованием циркулярного списка из srfi / 1.

  (require srfi/1)

  (define (shift xs k)
      (define n (length xs))
      (take (drop (apply circular-list xs) k) n))

Answer 4

Вот что-то похожее:

(define (addn value n)
  (let loop ((value value) (n n))
    (if (zero? n)
        value
        (loop (add1 value) (- n 1)))))

(addn 5 3)
; ==> 8

Теперь вы можете сделать абстракцию:

(define (repeat proc)
  (lambda (v n)
    ...))
(define addn (repeat add1))

(addn 5 3)
; ==> 8

(define shift-k-left (repeat shift-left))
(shift-k-left ’(1 2 3) 2)
; ==> (3 1 2)

Излишне говорить, что repeat очень похоже на add1.

Примечание: присвоение имени отключено. Ваша реализация больше «вращается», чем «смещается». shift-left на самом деле больше похоже на cdr, чем ваша реализация.