在球拍列表中删除第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))))))