ラケットのリストの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))))))