在球拍列表中刪除第n個元素的功能版本

Question

我想獲取從原始列表中刪除了第n個版本的列表。我可以管理以下代碼，這是必要的：

(define (list-removeN slist n) 
    (define outl '()) 
    (for ((i (length slist))) 
    (when (not (= i n)) 
     (set! outl (cons (list-ref slist i) outl)))) 
    (reverse outl)) 

什麼可以是這樣的功能等同？我嘗試了/ list，但是我必須在該位置插入#f或者刪除哪個不是很理想，因爲#f或者可能出現在列表中的其他位置。

Answer 1

您可以使用累加器遞歸執行此操作。像

#lang racket 

(define (remove-nth lst n) 
    (let loop ([i 0] [lst lst]) 
    (cond [(= i n) (rest lst)] 
      [else (cons (first lst) (loop (add1 i) (rest lst)))]))) 

(remove-nth (list 0 1 2 3 4 5) 3) 
(remove-nth (list 0 1 2 3) 3) 
(remove-nth (list 0 1 2) 0) 

某事，這會產生

'(0 1 2 4 5) 
'(0 1 2) 
'(1 2) 

您可以用for/list做，但這個版本橫貫因爲length通話清單的兩倍。

(define (remove-nth lst n) 
    (for/list ([i (length lst)] 
      [elem lst] 
      #:when (not (= i n))) 
    elem)) 

還有split-at，但同樣因爲它創造了兩個列表，並追加他們可能不會像最佳。

(define (remove-nth lst n) 
    (let-values ([(left right) (split-at lst n)]) 
    (append left (rest right)))) 

Answer 2

一個典型的滾動你自己的遞歸實現，並使用O（n）時間和O（n）空間。

(define (remove-nth lst i) 
    (let aux ((lst lst) (i i)) 
    (cond ((null? lst) '())  ;; what if (< (length lst) i) 
      ((<= i 0) (cdr lst)) ;; what if (< i 0) 
      (else (cons (car lst) 
         (aux (cdr lst) (sub1 i))))))) 

使用srfi-1的append-reverse的交互式版本。 O（n）時間和O（1）空間。

(define (remove-nth lst i) 
    (let aux ((lst lst) (i i) (acc '())) 
    (cond ((null? lst) (reverse acc))    ;; what if (< (length lst) i) 
      ((<= i 0) (append-reverse acc (cdr lst))) ;; what if (< i 0) 
      (else (aux (cdr lst) (sub1 i) (cons (car lst) acc))))))