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

我在做什麼錯？有沒有更好的方法來寫入推送，以便在最後添加元素並彈出，以便元素從第一個被刪除？

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寫的最後一個版本除外，解決方案效率非常低。例如，如果你做什麼西弗提示：

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

那麼這個副本整個隊列 - 這意味着，增加了項目的隊列中的循環將複製這一切在每個另外，產生了大量的GC的垃圾（想想在循環中將字符附加到字符串的末尾）。 「未知（谷歌）」解決方案修改列表並在其末尾添加一個指針，因此它避免了生成垃圾收集，但效率仍然很低。

Jonas寫的解決方案是這樣做的常見方法 - 保持指向列表末尾的指針。但是，如果您想在PLT方案中執行該操作，則需要使用可變對：mcons，mcar，mcdr，set-mcar!，set-mcdr!。從版本4.0出來以後，PLT中的常見對是不可變的。

Answer 2

你在那裏做的只是在本地修改「隊列」，所以結果不在定義範圍之外。這是因爲，在計劃中，所有東西都是通過價值傳遞的，而不是通過引用。而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) 

問題依賴於事，在計劃，它的數據和操作如下無副作用規則

因此，對於一個真正的隊列，我們​​希望的可變性，我們沒有。所以我們必須試着繞過它。

因爲一切都是通過值在方案通過，如參考反對，事情保持本地和保持不變，沒有副作用。因此，我選擇創建一個全球性的隊列，這是規避這種方式，通過全局應用我們的更改結構，而不是通過任何東西。

在任何情況下，如果你只需要1個隊列，儘管這種方法內存密集，但這種方法仍可以正常工作，因爲每次修改結構時都要創建一個新對象。

爲了獲得更好的結果，我們可以使用宏來自動創建隊列。

Answer 3

1. 你只是設置什麼是綁定到詞彙變量a-list。該函數退出後，該變量不再存在。

2. cons使一個新的缺點細胞。 cons單元由兩部分組成，稱爲car和cdr。列表是一系列的cons單元格，每輛車都有一些價值，每個cdr指向相應的下一個單元格，最後一個cdr指向零。當您編寫(cons a-list x)時，會創建一個新的缺陷單元，其中參考車中的a-list，以及在cdr中的x，這很可能不是您想要的。

3. push和pop通常被理解爲對稱操作。當你將某些東西推到列表上（作爲一個堆棧運行），那麼當你之後直接彈出這個列表時，你希望它能夠恢復。由於列表始終是在開頭引用的，因此您希望通過執行(cons x a-list)來推送列表。

4. IANAS（我不是一個有計劃的），但我認爲，最簡單的方法來得到你想要的是讓push宏（使用define-syntax），其擴展到(set! <lst> (cons <obj> <lst>))。否則，您需要將參考傳遞到push函數的列表。 pop類似。傳遞引用可以通過包裝到另一個列表中完成。

Answer 4

斯萬特是正確的，使用宏是慣用方法。

這是一個沒有宏的方法，但是在不利的方面，你不能使用普通列表作爲隊列。 至少與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 5

我想你試圖實施queue。這可以通過多種方式完成，但是如果您希望插入操作和刪除操作都在恆定時間內執行，則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) 

這幾乎對象計劃面向對象編程！您可以將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)) 

編輯：

由於Eli指出，對在默認情況下是immutable PLT計劃，這意味着沒有set-car!和set-cdr!。要使代碼在PLT方案中工作，您必須改用mutable pairs。在標準方案（R4RS，R5RS或R6RS）中，代碼應該不加修改地工作。

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) 

請注意，即使列表在Racket中不可變，它也可以工作。只需通過調整指針即可從列表中「彈出」一個項目。