How do I write Push and Pop in Scheme?

lisp, racket, scheme

Solution

This is a point about using mutation in your code: there is no need to jump to macros for that. I'll assume the stack operations for now: to get a simple value that you can pass around and mutate, all you need is a wrapper around the list and the rest of your code stays the same (well, with the minor change that makes it do stack operations properly). In PLT Scheme this is exactly what boxes are for:

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

Note also that you can use `begin0` instead of the `let`:

(define (pop a-list)
  (begin0 (first (unbox a-list))
    (set-box! a-list (rest (unbox a-list)))))

As for turning it into a queue, you can use one of the above methods, but except for the last version that Jonas wrote, the solutions are very inefficient. For example, if you do what Sev suggests:

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

then this copies the whole queue -- which means that a loop that adds items to your queue will copy it all on each addition, generating a lot of garbage for the GC (think about appending a character to the end of a string in a loop). The "unknown (google)" solution modifies the list and adds a pointer at its end, so it avoids generating garbage to collect, but it's still inefficient.

The solution that Jonas wrote is the common way to do this -- keeping a pointer to the end of the list. However, if you want to do it in PLT Scheme, you will need to use mutable pairs: `mcons`, `mcar`, `mcdr`, `set-mcar!`, `set-mcdr!`. The usual pairs in PLT are immutable since version 4.0 came out.

Problem

Right now I have ``` (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)) ``` But I get this 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) ``` What am I doing wrong? Is there a better way to write push so that the element is added at the end and pop so that the element gets deleted from the first?

Original source