(1 2 3. #) - heapsort

Question

Я попытался реализовать «кучу пар» со всеми регулярными операциями (merge, delete-min и т. Д.), Тогда мне было предложено написать функцию, которая сортировала бы список с использованием моей недавно построенной реализации кучи. К сожалению, кажется, что идет не так коснуться ...

Вот соответствующий код:

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

И вот некоторые селекторы, которые могут помочь вам понять код:

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

Теперь позволяет получить к проблеме: когда я запускаю «heapsort», он возвращает отсортированный список с «void», как вы можете видеть:

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

.. Я могу исправить?

С уважением, Superguay

Answer 1

Поскольку это домашнее задание, я вам скажу, процесс, я использовал, чтобы найти ошибку. Дайте мне знать, если вы все еще застряли.

Честно говоря, это слишком много кода для всестороннего анализа * в вопросе переполнения стека. Поэтому я должен использовать подсказки из вывода. В частности, у вас есть список с пустотой в нем. И это в конце, в неправильном списке. Это означает две вещи:

1. У вас есть функция, которая не возвращает значение. Две вещи, которые вызывают это: (1) написание if только с одной веткой - ветка else вернет пустоту - или (2) прекратит вашу функцию с display, которая возвращает void.
2. Последнее, что вы сделали, это cons. Возможно, вы хотели сохранить consing или, может быть, вы имели ввиду cons on() вместо этого, чтобы закончить список должным образом.

Итак: первым шагом является поиск кода для всех видов использования cons. Ваши селекторы выглядят отлично. Это оставляет две ветви в heap-merge и cons в heapsort. Все три звонка в cons используют функции, чтобы получить их cdr.

Итак, следующий шаг - посмотреть на heap-get-subheaps и aux, чтобы узнать, имеет ли один путь кода, который не возвращает значение. Возможно, у вас есть некоторые отладочные заявления, оставленные по ошибке. Или, может быть, у вас есть if, у которого есть только истинная ветка, и вы забыли ложную ветвь.

---

* Примечание. Большинство схем имеют настолько мало возможностей для отладки, что эвристика - ваш лучший выбор в любом случае. Это приобретенное умение.