向列表中添加元素

Question

我正在尝试在Scheme中实现一个过程，该过程将在位置i处添加一个元素x到现有列表中。这是我想出来的：

(define empty-list '())
(define (add i x L)
  (cond ((null? L) (set! L (list x)))
        ((= i 0)(set! L (cons x L)))
        (else (set! L (cons (car L)
                             (add (- i 1) x (cdr L))))
      )))

(add 0 1 empty-list) -> returns ()
(add 1 2 empty-list) -> returns ()
(add 2 3 empty-list) -> returns ()

代码不会更新现有列表。但是，如果我只运行(set! empty-list (list 1))或(set! empty-list (cons 2 empty-list))，它就能正常工作。我正在努力理解我做错了什么。

Answer 1

在使用set!时，您不会更改实际值，而是为最具体的绑定分配一个新值。在JavaScript中，它的工作原理相同：

function add (arr, element) {
  arr = arr.concatenate([element]);
  return arr;
}

const test = [1, 2, 3];
add(test, 4); // => [1, 2, 3, 4]
test;         // => [1, 2, 3]

Scheme中的这类过程通常不会发生变化。如果您删除带有该值的set!，它将返回正确的值：

(define (add i x L)
  (cond 
    ((null? L) (list x)) ; might not be at correct position
    ((= i 0) (cons x L))
    (else (cons (car L) (add (- i 1) x (cdr L))))))

(add 1 'b '(a c)) ; ==> (a b c)

Answer 2

在Scheme中，像许多函数式语言一样，我们通过使用更新的参数调用递归函数来更新状态。

(define (add i x l)
  ;; handle base cases outside of recursion, such as
  ;; if the starting list is empty, `i` is disregarded etc.
  (cond [(null? l) (cons x l)]
        [(null? (cdr l))
         (if (<= i 0)
             (cons x l)
             (append l (list x)))]
        [else
         (let recur ([start l] [index 0])
           ;; base case
           (if (= index i)
               (cons x start)
               ;; this is how states are updated
               (cons (car start) (recur (cdr start) (+ index 1)))))]))


;; > (add 3 'newguy '(mary peter nguyen joo kim))
;; '(mary peter nguyen newguy joo kim)