Тут короче понадобилось заюзать мне binary heap в racket и захотел я это сделать с использованием стандартных схем итерации через for-iterations.
Однако текущая binary heap не реализует нужный интерфейс (stream?).

Поэтому кое-чего нужно доопределить. К счастью, в racket это сделать достаточно просто.

Необходимо задать структуру, реализующую три функции: stream-empty? stream-first и stream-rest
(тест на пустоту потока, получение элемента из головы и хвоста)

(define-struct hstream (v)
#:methods gen:stream
[(define (stream-empty? st)
(eq? (heap-count (hstream-v st)) 0))
(define (stream-first st)
(heap-min (hstream-v st)))
(define (stream-rest st)
(begin (heap-remove-min! (hstream-v st))
(hstream (hstream-v st))))])

простой пример:

> (define h1 (make-heap <))
> (heap-add! h1 8)
> (heap-add! h1 11)
> (heap-add! h1 2)

> (for/list ([x h1]) x)
for: expected a sequence for x, got something else: #<heap>

> (for/list ([x (hstream h1)]) x)
'(2 8 11)

#tioege

add comment recommend bookmark subscribe