Как удалить первый и последний элемент в списке в Racket с помощью рекурсии

Question

По сути, я пытаюсь удалить первый и последний элемент в списке. В настоящее время я могу определить, как удалить последний элемент в списке, но я изо всех сил пытаюсь удалить первый элемент в списке с последним элементом в списке.

Вот код, который у меня есть. Есть ли способ изменить мой код, чтобы я мог включить удаление первого элемента в списке.

(define (rid L)
  (cond
    [(empty? L) '()]
    [(empty? (rest L)) '()]
    [(cons (first L) (rid (rest L)))]))

Вот результаты, которые я ожидаю с моим кодом

(check-expect (rid (list 1 2 3 4 5)) (list 2 3 4))
(check-expect (rid (list "cat" "dog" "giraffe")) (list "dog"))

Answer 1

Просто для удовольствия - в Racket вы можете решить эту проблему без использования явной рекурсии.Всегда старайтесь использовать существующие процедуры для решения ваших проблем:

(define (rid L)
  (rest (drop-right L 1)))

(rid '(1 2 3 4 5 6))
=> '(2 3 4 5)

Answer 2

При использовании многих рекурсивных алгоритмов нередко их реализуют с помощью двух процедур: одной для установки начальных условий и второй для выполнения реальной рекурсии, например:

(define (rid-inner li)
  (cond
    [(empty? li) '()]
    [(empty? (rest li)) '()]
    [(cons (first li) (rid-inner (rest li)))]))

(define (rid1 L)
  (define r (if (empty? L) '() (rest L)))
  (rid-inner r))

С помощью (define r (if (empty? L) '() (rest L))) мы удаляем первый элемент списка; для этого шага рекурсия не нужна. Затем мы определяем ту же процедуру, что и раньше, с другим именем и вызываем ее с нашим новым списком, в котором уже удален первый элемент. Если вы хотите удалить первый элемент, просто удалите первый элемент; не задумывайся об этом :).

В таком языке, как Racket, который допускает замыкания и вложенные процедуры, вам даже не нужно определять обе процедуры в верхней "глобальной" области модуля; просто определите вашу рекурсивную процедуру внутри вашей начальной процедуры и вызовите ее оттуда. Пример:

(define (rid2 L)
  (define r (if (empty? L) '() (rest L)))
  (define (rid-inner li)
    (cond
      [(empty? li) '()]
      [(empty? (rest li)) '()]
      [(cons (first li) (rid-inner (rest li)))]))
  (rid-inner r))

Другой, несколько более чистый способ сделать это - использовать именованный let, который позволяет нам одновременно устанавливать наши начальные условия, создавать именованную процедуру, а затем немедленно вызывать эту процедуру изнутри себя. Мы делаем это так:

(define (rid3 L)
  (let rid-inner ([li (if (empty? L) '() (rest L))])
    (cond
      [(empty? li) '()]
      [(empty? (rest li)) '()]
      [(cons (first li) (rid-inner (rest li)))])))

Для тех, кто не знаком с Ракетом, Схемой или связанным с ним Лиспом, имя let в rid3 поначалу может показаться более загадочным, поскольку в действительности оно делает две или три вещи одновременно. Вы можете найти документы для этого здесь . Не обманывайте себя, это работает точно так же, как rid2. Имя let существует именно потому, что этот шаблон очень распространен.

Answer 3

рекурсивная версия хвостового вызова

(define (rid lst (acc '()))
  (cond ((empty? lst) acc)
        ((empty? (cdr lst)) (cdr (reverse acc)))
        (else (rid (cdr lst) (cons (car lst) acc)))))

с элементарной росписью (не самый эффективный)

(define (rid1 lst)
  (cdr (reverse (cdr (reverse lst))))

Answer 4

(define (rid L)
  (if (< (length L) 3)
      '()
      (reverse (rest (reverse (rest L))))))

;;; recursion inside and more general
;;; you can setting which position 0~n-1 you want to remove

(define (rid-v2 L)
  (local ((define remove-index-list (list 0 (- (length L) 1)))
          (define (auxf L k)
            (cond
              [(empty? L) '()]
              [(memq k remove-index-list) (auxf (rest L) (+ k 1))]
              [else (cons (first L)
                          (auxf (rest L) (+ k 1)))])))
    (auxf L 0)))