lisp - Scheme中的Push和Pop怎么写？

Question

现在我有

(define (push x a-list)
  (set! a-list (cons a-list x)))

(define (pop a-list)
  (let ((result (first a-list)))
    (set! a-list  (rest a-list))
    result))

但我得到了这个结果:

Welcome to DrScheme, version 4.2 [3m].
Language: Module; memory limit: 256 megabytes.
> (define my-list (list 1 2 3))
> (push 4 my-list)
> my-list
(1 2 3)
> (pop my-list)
1
> my-list
(1 2 3)

我做错了什么？有没有更好的方法来编写 push 以便在末尾添加元素并 pop 以便从第一个删除元素？

Answer 1

这是关于在代码中使用突变的要点:没有必要为此跳转到宏。我现在假设堆栈操作:要获得一个可以传递和改变的简单值，您所需要的只是列表周围的包装器，其余代码保持不变(好吧，进行微小的更改它正确地执行堆栈操作)。在 PLT Scheme 中，这正是 boxes 的用途:

(define (push x a-list)
  (set-box! a-list (cons x (unbox a-list))))

(define (pop a-list)
  (let ((result (first (unbox a-list))))
    (set-box! a-list (rest (unbox a-list)))
    result))

另请注意，您可以使用 begin0 代替 let:

(define (pop a-list)
  (begin0 (first (unbox a-list))
    (set-box! a-list (rest (unbox a-list)))))

至于把它变成一个队列，你可以使用上面的方法之一，但是除了Jonas写的最后一个版本，其他解决方案都非常低效。例如，如果您按照 Sev 的建议进行操作:

(set-box! queue (append (unbox queue) (list x)))

然后这会复制整个队列——这意味着将项目添加到队列的循环将在每次添加时复制所有项目，为 GC 生成大量垃圾(考虑附加一个字符到循环中字符串的末尾)。 “unknown (google)”解决方案修改了列表并在其末尾添加了一个指针，因此它避免了生成垃圾以进行收集，但仍然效率低下。

Jonas 编写的解决方案是执行此操作的常用方法——保留指向列表末尾的指针。但是，如果你想在 PLT Scheme 中这样做，你将需要使用可变对:mcons、mcar、mcdr、 set-mcar!, set-mcdr!.自 4.0 版问世以来，PLT 中的常用对是不可变的。