在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 方案中，这正是框的用途：

(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（考虑在循环中将一个字符附加到字符串的末尾）。 “未知（google）”解决方案修改了列表并在其末尾添加了一个指针，因此它避免了生成垃圾来收集，但它仍然是低效的。

Jonas 编写的解决方案是执行此操作的常用方法 - 保留指向列表末尾的指针。 但是，如果您想在 PLT 方案中执行此操作，则需要使用可变对：mcons、mcar、mcdr、set-mcar！，set-mcdr！。 自 4.0 版本发布以来，PLT 中的常用对是不可变的。

Answer 2

1. 您只是设置绑定到词法变量a-list的内容。 函数退出后，该变量不再存在。

2. cons 创建一个新的 cons 单元。 cons 单元由两部分组成，分别称为 car 和 cdr。 列表是一系列 cons 单元，其中每辆车都保存一些值，每个 cdr 指向各自的下一个单元，最后一个 cdr 指向 nil。 当您编写 (cons a-list x) 时，这会创建一个新的 cons 单元，并引用汽车中的 a-list 和 x 在 cdr 中，这很可能不是您想要的。

3. push 和 pop 通常被理解为对称操作。 当您将某些内容推入列表（充当堆栈）时，您希望在之后直接弹出该列表时将其取回。 由于列表总是在其开头被引用，因此您希望通过执行 (cons x a-list) 将其推送到那里。

4. IANAS（我不是计划者），但我认为获得你想要的最简单的方法是使 push 成为一个宏（使用 define-syntax）扩展为 (set!(cons))。 否则，您需要将对列表的引用传递给push函数。 类似的情况也适用于 pop。 传递引用可以通过包装到另一个列表中来完成。

Answer 3

Svante 是正确的，使用宏是惯用的方法。

这是一种没有宏的方法，但缺点是您不能使用普通列表作为队列。
至少适用于 R5RS，导入正确的库后应该适用于 R6RS。

(define (push x queue)
  (let loop ((l (car queue)))
    (if (null? (cdr l))
      (set-cdr! l (list x))
      (loop (cdr l)))))

 (define (pop queue)
   (let ((tmp (car (car queue))))
     (set-car! queue (cdr (car queue)))
     tmp))

(define make-queue (lambda args (list args)))

(define q (make-queue 1 2 3))

(push 4 q)
q
; ((1 2 3 4))
(pop a)
; ((2 3 4))
q

Answer 4

我想您正在尝试实现队列。 这可以通过多种方式完成，但如果您希望插入和删除操作都在恒定时间 O(1) 内执行，则必须保留对 前面和后面 的引用队列。

您可以将这些参考文献保存在 cons cell 或者像我的例子一样，包裹在一个闭包中。

术语 push 和 pop 通常在处理堆栈时使用，因此我将它们更改为 enqueue 和 dequeue在下面的代码中。

(define (make-queue)
  (let ((front '())
        (back '()))
    (lambda (msg . obj)
      (cond ((eq? msg 'empty?) (null? front))
            ((eq? msg 'enqueue!) 
             (if (null? front)
                 (begin 
                   (set! front obj)
                   (set! back obj))
                 (begin
                   (set-cdr! back obj)
                   (set! back obj))))
            ((eq? msg 'dequeue!) 
             (begin
               (let ((val (car front)))
                 (set! front (cdr front))
                 val)))
            ((eq? msg 'queue->list) front)))))

make-queue 返回一个过程，该过程将队列的状态包装在变量 front 和 back 中。 该过程接受不同的消息，这些消息将执行队列数据结构的过程。

这个过程可以这样使用：

> (define q (make-queue))
> (q 'empty?)
#t
> (q 'enqueue! 4)
> (q 'empty?)
#f
> (q 'enqueue! 9)
> (q 'queue->list)
(4 9)
> (q 'dequeue!)
4
> (q 'queue->list)
(9)

这几乎是Scheme中的面向对象编程！ 您可以将 front 和 back 视为队列类的私有成员，并将消息视为方法。

调用约定有点落后，但很容易将队列包装在更好的 API 中：

(define (enqueue! queue x)
   (queue 'enqueue! x))

(define (dequeue! queue)
  (queue 'dequeue!))

(define (empty-queue? queue)
  (queue 'empty?))

(define (queue->list queue)
  (queue 'queue->list))

编辑：

As Eli 指出，对是 在 PLT 方案中默认是不可变的，这意味着没有 set-car! 和 set-cdr! 。 为了让代码在 PLT 方案中工作，您必须使用可变对。 在标准方案（R4RS、R5RS 或 R6RS）中，代码应无需修改即可工作。

Answer 5

对列表进行操作的push和pop宏在许多Lispy语言中都可以找到：Emacs Lisp、GaucheScheme、CommonLisp、ChickenScheme（在杂项宏蛋中）、Arc等。

Welcome to Racket v6.1.1.
> (define-syntax pop!
  (syntax-rules ()
    [(pop! xs)
     (begin0 (car xs) (set! xs (cdr xs)))]))
> (define-syntax push!
  (syntax-rules ()
    [(push! item xs)
     (set! xs (cons item xs))]))
> (define xs '(3 4 5 6))
> (define ys xs)
> (pop! xs)
3
> (pop! xs)
4
> (push! 9000 xs)
> xs
'(9000 5 6)
> ys  ;; Note that this is unchanged.
'(3 4 5 6)

请注意，即使列表在球拍。 只需调整指针即可从列表中“弹出”项目。

Answer 6

您所做的只是在本地修改“队列”，因此结果在定义范围之外不可用。 这是因为，在方案中，所有内容都是按值传递，而不是按引用传递。 而且Scheme结构是不可变的。

(define queue '()) ;; globally set

(define (push item)
  (set! queue (append queue (list item))))

(define (pop)
  (if (null? queue)
      '()
      (let ((pop (car queue)))
        (set! queue (cdr queue))
        pop)))

;; some testing
(push 1)
queue
(push 2)
queue
(push 3)
queue
(pop)
queue
(pop)
queue
(pop)

问题在于，在Scheme中，数据及其操作遵循无副作用规则

因此，对于真正的队列，我们​​需要可变性，即我们没有。 所以我们必须尝试并规避它。

由于方案中的所有内容都是按值传递，而不是通过引用传递，因此事物保持本地状态并保持不变，没有副作用。因此，我选择创建一个全局队列，这是一种规避此问题的方法，通过全局应用我们对结构的更改，而不是传递任何内容。

在任何情况下，如果您只需要 1 个队列，则此方法可以正常工作，尽管它是内存密集型，因为每次修改结构时都会创建一个新对象。

为了获得更好的结果，我们可以使用宏来自动创建队列。