5
\$\begingroup\$

From SICP:

Exercise 3.22. Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

Complete the definition of make-queue and provide implementations of the queue operations using this representation.

I wrote the following solution:

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! ptr) (set! front-ptr ptr))
    (define (set-rear-ptr! ptr) (set! rear-ptr ptr))
    (define (empty?) (null? front-ptr))
    (define (front-queue) 
      (if (empty?)
          (error "FRONT called with an empty queue" front-ptr)
          (car front-ptr)))
    (define (insert! item)
      (let ((new-pair (cons item '())))
        (cond ((empty?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair)
               dispatch)
              (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)
               dispatch))))
    (define (delete!)
      (cond ((empty?)
             (error "DELETE! called with an empty queue" first-ptr))
            (else
             (set-front-ptr! (cdr front-ptr))))
      dispatch)
    (define (print) front-ptr)
    (define (dispatch m)
      (cond ((eq? m 'insert!) insert!)
            ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'empty?) empty?)
            ((eq? m 'delete!) delete!)
            ((eq? m 'print) print)
            (else (error "No such procedure: dispatch" m))))
    dispatch))

(define q1 (make-queue))
((((q1 'insert!) 'a) 'print))
((((q1 'insert!) 'b) 'print))
((((q1 'delete!)) 'print))
((((q1 'delete!)) 'print))

How can it be improved?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Looking through your questions, you have a lot of titles that unnecessarily contain tags. You should only use titles to briefly describe what your program/method does. \$\endgroup\$
    – syb0rg
    Commented Jan 17, 2014 at 4:48

1 Answer 1

1
\$\begingroup\$

You did not provide implementations of the queue operations using this representation. In SICP this usually refers to syntactic sugar to make working with a data structure less awkward, e.g.

(define (queue-insert! q item)
    ((q 'insert!) item) )

Also I would prefer different operation names, e.g.

append! instead of insert! front instead of front-ptr ...

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.