Improving a priority queue sketch in Racket/Scheme

Question

I just put together the skeletons for a priority queue using a binary heap in racket/scheme. Using racket/scheme is all about the educational experience and I was wondering if anyone wants to critique and improve the code. Bug reports are welcome

;; priority queues operations on integer values

(define (heap)
  (let ((the-heap (make-vector 10)) (next-free 1))

(define (swim val) 
  (begin 
    (vector-set! the-heap next-free val)
    (set! next-free (+ next-free 1))
    (let loop ((i (- next-free 1)))
      (if (and (< (vector-ref the-heap (quotient i 2)) (vector-ref the-heap i)) (> (quotient i 2) 0))
          (begin 
            (exch the-heap i (floor (/ i 2)))
            (loop (floor (/ i 2))))
        the-heap))))

(define (sink index) 
  ;; a call to this method is used to re-establish order within the
  ;; heap by 'sinking' the value rooted at index to its right position
  ;; within the whole heap
  (let loop ((node index) (kid (* 2 index)))
    (if (<= kid next-free)
        (let ((larger-kid (if (> (vector-ref the-heap kid) (vector-ref the-heap (+ kid 1)))
                                 kid
                                 (+ kid 1))))
          (if (> (vector-ref the-heap larger-kid) (vector-ref the-heap node))
              (begin
                (exch the-heap node larger-kid)
                (loop larger-kid (* 2 larger-kid)))
              the-heap))
          (newline))))

(define (delete-max)
  ;; delete and return the maximum value in the heap.
  ;; add the last item on the heap to the root position 
  ;; sink to re-establish order within the heap of the heap and call
  ;; 
  (begin 
    (let ((val (vector-ref the-heap 1)))
      (vector-set! the-heap 1 (vector-ref the-heap (- next-free 1)))
      (set! next-free (- next-free 1))
      (vector-set! the-heap next-free 0)
      (sink 1)
      val)))


(define (put value) 
  (swim value))

(define (size) 
  (vector-length the-heap))

(define (empty?) 
  (= next-free 1))

(define (exch vec lo j)
  (let ((lo-val (vector-ref vec lo)) (j-val (vector-ref vec j)))
    (begin
      (vector-set! vec lo j-val)
      (vector-set! vec j lo-val))))

(define (dispatch message . arg)
  (cond 
    ((eq? message 'delete-max) (delete-max))
    ((eq? message 'put) (put (car arg)))
    ((eq? message 'size) size)
    ((eq? message 'heap) the-heap)
    ((eq? message 'empty?) empty?)))
dispatch))

Answer 1

Here are some general points before I start on more specific points:

• I don't see any unit tests. Racket programmers often write many unit tests for each function. You can use the module+ construct and rackunit to easily write internal unit tests.
• Indentation is important for clarity. I couldn't tell that everything was internal to heap at first because of the lack of indentation. Also, you can replace some of the lets with internal defines and make some of the internal functions into top-level functions to reduce right-ward drift.

More specific points:

• It looks like you're using a dispatch function with internal state to keep track of the priority queue state. The more natural thing to do in Racket would be to create a new datatype using struct. This way, your implementation details don't leak through.
• You use a dispatch function as the entry point to your simulated object. Simulating OO style in this fashion is not a very natural thing to do in Racket. Racket programmers tend to either use (1) the built-in classes & objects or (2) have a functional API with a function for each operation.
• You use begin to sequence multiple effecting operations inside functions. These are actually unnecessary since Racket functions can have as many expressions in the body as you like.

Hope that helps. Cheers.