(1 2 3 . #<void>)- heapsort

Question

I tried to implement a "pairing heap" with all the regular operations (merge, delete-min etc.), then I've been requested to write a function that would sort a list using my newly constructed heap implementation. Unfortunately it seems that someting goes wrong...

Here's the relevant code:

(define (heap-merge h1 h2)
  (cond ((heap-empty? h1) h2)
    ((heap-empty? h2) h1)
    (else (let ((min1 (heap-get-min h1))
        (min2 (heap-get-min h2)))
        (if ((heap-get-less h1) min1 min2)
        (make-pairing-heap (heap-get-less h1) min1 (cons h2 (heap-get-subheaps h1)))
        (make-pairing-heap (heap-get-less h1) min2 (cons h1 (heap-get-subheaps h2))))))))

(define (heap-insert element h)
(heap-merge (make-pairing-heap (heap-get-less h) element '())
       h))

(define (heap-delete-min h)
(define (merge-in-pairs less? subheaps)
(cond
  ((null? subheaps) (make-heap less?))
  ((null? (cdr subheaps)) (car subheaps))
  (else (heap-merge (heap-merge (car subheaps) (cadr subheaps))
                            (merge-in-pairs less? (cddr subheaps))))))
(if (heap-empty? h) (error "expected pairing-heap for first argument, got an empty heap ")
  (merge-in-pairs (heap-get-less h) (heap-get-subheaps h)))) 

(define (heapsort l less?)
(let aux ((h (accumulate heap-insert (make-heap less?) l)))
(if (not (heap-empty? h))
     (cons (heap-get-min h) 
    (aux (heap-delete-min h)))))) 

And these are some selectors that may help you to understand the code:

(define (make-pairing-heap less? min subheaps) 
(cons less? (cons min subheaps)))
(define (make-heap less?)
(cons less? '()))
(define (heap-get-less h)
(car h))
(define (heap-empty? h)
(if (null? (cdr h)) #t #f))

Now lets get to the problem: When i run 'heapsort' it returns the sorted list with "void", as you can see:

> (heapsort (list 1 2 3) <)
(1 2 3 . #<void>)

..HOW CAN I FIX IT?

Regards, Superguay

Answer 1

Since this is homework, I'll tell you the process I used to find the bug. Let me know if you're still stuck.

Honestly, this is too much code to analyse* in-depth in a Stack Overflow question. So I have to use clues from the output. Specifically, you have a list with a void in it. And it's at the end, in an improper list. That means two things:

1. You have a function that doesn't return a value. Two things that cause this are (1) writing an if with only one branch--the else branch will return void--or (2) ending your function with a display, which returns void.
2. The last thing you did was cons. You might have meant to keep consing or maybe you meant to cons on '() instead to end the list properly.

So: first step is to search the code for all uses of cons. Your selectors look fine. That leaves the two branches in heap-merge and the cons in heapsort. All three calls to cons use functions to get their cdr.

So: next step is to look at heap-get-subheaps and aux to see if either one has a code path that doesn't return a value. Maybe you have some debugging statements left in by mistake. Or maybe you have an if that only has the true branch and you forgot the false branch.

---

*Note: Most Schemes have so few debugging features that heuristics are your best bet anyway. It's an acquired skill.