CODEWITHSUNDEEP
schemeracket
rnso
rnso

Reputation: 24623

Functional version of deleting nth element in a list in Racket

I want to get a list which has nth version deleted from the original list. I could manage following code which is imperative: 

(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))

What can be the functional equivalent of this? I tried for/list, but I have to insert #f or at that position, removing which is not ideal because #f or may occur at other positions in list also.

Upvotes: 0

Views: 1454

Answers (2)

Gibstick
Gibstick

Reputation: 737

You can do it recursively with an accumulator. Something like

#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)

This produces

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

You could do it with for/list but this version traverses the list twice because of the length call.

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

There's also split-at, but again this may not be as optimal as it creates two lists and appends them.

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

Upvotes: 2

Sylwester
Sylwester

Reputation: 48775

A typical roll your own implementation that is recursive and uses O(n) time and O(n) space.

(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)))))))

A interative version that uses append-reverse from srfi-1. O(n) time and O(1) space.

(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))))))

Upvotes: 2

Related Questions