How to write Push and Pop in Scheme?

Question

I have now

(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 is removed from the first?

Answer 1

This is a question about using mutations in your code: there is no need to move on to macros for this. I will take the following operations with the stack: to get a simple value that you can pass and mutate, all you need is a wrapper around the list, and the rest of your code remains the same (well, with minor changes that it makes correctly executes stack operations). In the PLT diagram, this is exactly what windows 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 that you can use begin0 instead of 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 latest version that Jonas wrote, the solutions are very inefficient. For example, if you do what Sev offers:

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

then this copies the whole queue, which means that the loop that adds the elements to your queue will copy all this on each addition, generating a lot of garbage for the GC (think about adding a character to the end of the line in the loop). The "google" solution changes the list and adds a pointer to the end, so it avoids generating garbage to collect, but it is still inefficient.

The solution Jonas wrote is a general way to do this - keep the pointer at the end of the list. However, if you want to do this on the PLT Scheme, you will need to use mutable pairs: mcons , mcar , mcdr , set-mcar! , set-mcdr! . Regular pairs in PLT are immutable since version 4.0 was introduced.

Answer 2

• You simply set what is associated with the lexical variable a-list . This variable no longer exists after the function exits.

• cons creates a new cons cell. The cons cell consists of two parts, which are called car and cdr . The list is a series of cons cells, where each car has a certain value, and each cdr points to the corresponding next cell, the last cdr points to nil. When you write (cons a-list x) , this creates a new cons cell with a link to a-list in the machine and x in cdr, which is most likely not what you want.

• push and pop are commonly understood as symmetric operations. When you click something on a list (function as a stack), you expect to return it when you immediately place this list. Since the list always refers to its beginning, you want to click there by doing (cons x a-list) .

• IANAS (I'm not Schemer), but I think the easiest way to get what you want is to make a push macro (using define-syntax ) that will expand to (set! <lst> (cons <obj> <lst>)) . Otherwise, you need to pass the link to your list to the push function. The same is true for pop . Link transfer can be done by transferring to another list.

Answer 3

Svante is true, using macros is an idiomatic method.

Here is a method without macros, but from the bottom you cannot use regular lists as queues. Works with R5RS at least should work in R6RS after importing the correct libraries.

 (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

I assume that you are trying to implement a queue . This can be done in several ways, but if you want the insert and delete operation to be performed at a constant time, O (1), you must save the link to the front and back of the queue.

You can save these links in a cons cell or, as in my example, wrapped in closure.

The terminology push and pop commonly used when working with stacks, so I changed them to enqueue and dequeue in the code below.

  (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 returns a procedure that wraps the state of the queue in the front and back variables. This procedure receives different messages that will execute the queue data structure procedures.

This procedure can be used as follows:

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

This is almost object-oriented programming on a schema! You can think of front and back as private members of the queue class, and messages as methods.

The calling conventions are slightly behind, but it's easy to port the queue to a more convenient 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))

Edit:

As Eli points out, pairs are immutable by default in the PLT scheme, which means there is no set-car! and set-cdr! . For code to work on the PLT Scheme, you must use mutable pairs instead. In the standard circuit (R4RS, R5RS or R6RS), the code should work without changes.

Answer 5

What you do only changes the "queue" only locally, so the result is not available outside the scope. This is because in the scheme everything is passed by value, and not by reference. Scheme Structures are immutable.

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

The problem is based on the fact that in the Scheme data and manipulations with it follow the rule without side effects

So, for the true lineup, we need variability that we don’t have. Therefore, we must try to circumvent it.

Since everything is transferred by the value in the scheme, unlike the link, everything remains local and remains unchanged, without side effects. So I decided to create a global queue, which is a way around this, applying our changes to the structure around the world, rather than skipping anything.

In any case, if you just need 1 queue, this method will work fine, although it is intensive, because you create a new object every time you change the structure.

To improve results, we can use a macro to automate queue creation.

Answer 6

The push and pop macros that work in lists are in many Lisp languages: Emacs Lisp, Gauche Scheme, Common Lisp, Chicken Scheme (in miscmacros egg), Arc, etc.

 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) 

Note that this works even if lists are immutable in Racket. The item "popped" out of the list by simply adjusting the pointer.