4

现在我有

(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 以便从第一个元素中删除元素？

4

6 回答 6

7

这是关于在代码中使用突变的一点：没有必要为此跳转到宏。我现在假设堆栈操作：要获得一个可以传递和变异的简单值，您只需要一个围绕列表的包装器，其余代码保持不变（嗯，稍作改动它正确地进行堆栈操作）。在 PLT Scheme 中，这正是盒子的用途：

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

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

于 2009-06-26T10:34:28.853 回答
5

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

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

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

  4. IANAS（我不是 Schemer），但我认为获得所需内容的最简单方法是制作push一个define-syntax扩展为(set! <lst> (cons <obj> <lst>)). 否则，您需要将对您的列表的引用push传递给该函数。类似的成立pop。传递引用可以通过包装到另一个列表中来完成。

于 2009-06-25T00:50:42.567 回答
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
于 2009-06-25T03:17:07.670 回答
1

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

您可以将这些引用保存在一个cons 单元格中，或者像我的示例中那样，将它们包裹在一个闭包中。

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

（定义（制作队列）
  （让（（前面'（））
        （背部 '（）））
    （拉姆达（味精。obj）
      (cond ((eq?msg 'empty?) (null?front))
            ((eq?msg '入队！)
             （如果（空？前面）
                 （开始
                   （设置！前 obj）
                   （设置！返回 obj））
                 （开始
                   （set-cdr！返回 obj）
                   （设置！返回 obj））））
            ((eq?msg '出队！)
             （开始
               (让 ((val (车前)))
                 (set!front (cdr front))
                 验证）））
            ((eq?msg 'queue->list) front)))))

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

这个过程可以这样使用：

> (定义 q (make-queue))
> (q'空？)
#t
> (q'入队！4)
> (q'空？)
＃F
> (q'入队！9)
> (q '队列->列表)
(4 9)
> (q'出队！)
4
> (q '队列->列表)
(9)

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

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

（定义（入队！队列 x）
   （队列'入队！x））

（定义（出队！队列）
  （队列'出队！））

（定义（空队列？队列）
  （队列'空？））

（定义（队列->列表队列）
  （队列'队列->列表））

编辑：

正如Eli指出的那样，在 PLT Scheme 中，pairs 默认是不可变的，这意味着没有set-car!and set-cdr!。要使代码在 PLT Scheme 中运行，您必须改用 可变对。在标准方案（R4RS、R5RS 或 R6RS）中，代码应该不加修改地工作。

于 2009-06-26T04:28:07.283 回答
0

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

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

于 2009-06-25T00:29:59.987 回答
0

对列表进行操作的 push 和 pop 宏可以在许多 Lisp 语言中找到：Emacs Lisp、Gauche Scheme、Common Lisp、Chicken Scheme（在 miscmacros egg 中）、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)

请注意，即使列表在 Racket 中是不可变的，这仍然有效。只需调整指针即可从列表中“弹出”一个项目。

于 2017-08-06T02:15:28.177 回答