如何在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,以便在结尾添加元素并弹出以便元素从第一个中删除？

Answer 1

这是关于在代码中使用变异的一点:没有必要为此跳转到宏.我现在假设堆栈操作:为了得到一个可以传递和变异的简单值,你需要的只是一个包装器,而你的代码的其余部分保持不变(好吧,这是一个微小的变化,使得它可以正确堆叠操作).在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生成大量垃圾(考虑在循环中将字符附加到字符串的末尾)."未知(google)"解决方案修改了列表并在其末尾添加了一个指针,因此它避免了生成要收集的垃圾,但它仍然效率低下.

Jonas编写的解决方案是执行此操作的常用方法 - 保持指向列表末尾的指针.不过,如果你想这样做的PLT的计划,你将需要使用可变双:mcons,mcar,mcdr,set-mcar!,set-mcdr!.自4.0版本发布以来,PLT中的常用对是不可变的.

Answer 2

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

2. cons制作一个新的利弊细胞.cons单元由两部分组成,称为car和cdr.列表是一系列缺点单元格,其中每个汽车保持一些值,每个cdr指向相应的下一个单元格,最后一个cdr指向nil.当你写作时(cons a-list x),这会创建一个新的cons单元格,其中包含对a-list汽车和xcdr 的引用,这很可能不是你想要的.

3. push和pop通常理解为对称操作.当您将某些内容推送到列表(作为堆栈)时,您希望在之后直接弹出此列表时将其恢复.由于列表始终在其开头引用,因此您希望通过执行来推送列表(cons x a-list).

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