#lang racket

;; replace : list num val -> list
;;  Replces one item in a list (with 0-based indexing)

;; This variant of `replace` mimics an
;; imperative "for (i=0;i<len;i++) ..." loop
;; that builds up a list from front to back. It
;; works and its functional, but it doesn't
;; follow the design recipe, and it turns out
;; to have quadratic running time.
#;
(define (replace l i v)
  (define (helper accl acci)
    (cond
      [(= acci (length l)) accl]
      [(= acci i) (helper (append accl (list v)) (+ acci 1))]
      [else (helper (append accl (list (list-ref l acci))) (+ acci 1))]))
  (helper '() 0))

;; This variant of `replace` is more typical functional
;; style. It follows the design recipe, and it runs in
;; linear time. The key idea is to adjust the index
;; by one while dropping an item off the front of the
;; list in a recursive call.
(define (replace l i v)
  (cond
    [(empty? l) empty]
    [(cons? l) (if (= i 0)
                   (cons v (rest l))
                   (cons (first l)
                         (replace (rest l) (- i 1) v)))]))

(module+ test
  (require rackunit)
  (check-equal? (replace '() 10 'x) '())
  (check-equal? (replace '(0 1 2 3 4 5) 3 'c) '(0 1 2 c 4 5)))