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

至于把它变成一个队列，你可以使用上面的方法之一，但不同的是乔纳斯所写的最后一个版本，该解决方案是非常低效的。例如，如果你做什么西弗提示：

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

那么这个副本的全部队列 - 这意味着，增加了项目的队列中的循环将复制这一切在每个另外，产生大量的垃圾，为GC（想想一个附加字符的字符串的在一个循环中的端部）。 “未知（谷歌）”解决方案修改了该列表，并在其端部增加了一个指针，所以它避免了产生垃圾收集，但它仍然是低效率的。

这乔纳斯写的解决方案是要做到这一点的常见的方法 - 保持的指针列表的末尾。不过，如果你想这样做的PLT的计划，你将需要使用可变双：mcons，mcar，mcdr，set-mcar!，set-mcdr!。在PLT通常对是不可变的，因为版本4.0出来。

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! <lst> (cons <obj> <lst>)). 。否则，您需要通过 参考 到您的列表 到 push 功能。类似的情况也适用于 pop. 。可以通过包装到另一个列表中来传递引用。

Answer 3

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

下面是没有宏的方法，但不利的一面是，你不能正常使用列表作为队列。 与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) 内执行，则必须保留对 正面和背面 队列的。

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

术语 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))

编辑：

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

Answer 5

您所做的只是在本地修改“队列”，因此结果在定义范围之外不可用。这是因为，在方案中，所有内容都是按值传递，而不是按引用传递。而且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 个队列，则此方法可以正常工作，尽管它会占用大量内存，因为每次修改结构时都会创建一个新对象。

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

Answer 6

在push和pop宏，列表上的操作，在许多Lispy语言中发现：的Emacs Lisp，左岸计划，Common Lisp的，鸡计划（在miscmacros蛋），弧等

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)

请注意，此作品即使名单是在球拍不变。一个项目是简单地通过调整一个指针“弹出”从列表中。