ハミング数

Gauche の data.heap モジュール を使ってハミング数を求めてみます。(効率は悪いです)

(use data.heap)
(use gauche.generator)

(define (hamming n)

  (define (gen)
    (generate
     (^[yield]
       (let1 heap (make-binary-heap)
         (binary-heap-push! heap 1)
         (let loop ()
           (let1 v (binary-heap-pop-min! heap)
             (yield v)
             (dolist (x '(2 3 5))
               (binary-heap-push! heap (* v x)))
             (loop)))))))

  ;; 連続する重複値は流さないジェネレータ
  (define (distinct g)
    (let1 head (g)
      (generate
       (^[yield]
         (yield head)
         (let loop ((prev head))
           (let1 curr (g)
             (unless (eqv? prev curr)
               (yield curr))
             (loop curr)))))))

  (generator->list (distinct (gen)) n))

実行結果です。

gosh> (hamming 30)
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80)

参考: