[plt-scheme] From hash-table to generator

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Mon May 7 16:45:55 EDT 2007

I have implemented sets on top of hash tables.

A SET is a

    (define-struct set (ht))

where ht is hash-table from strings to #t.

I'd like to extend srfi-42 with a :set generator,
as an example:

  > (list-ec (:set x (list->set 1 2 3))
             x)
  (1 2 3)

My first version converted the hash-table to a list
and expanded :set into a :list :

(define-syntax :set
   (syntax-rules (index)
     ((:set cc var (index i) arg)
      (:parallel cc (:set var arg) (:integers i)) )
     ((:set cc var arg)
      (:list cc var (set->list arg)))))

where

(define (hash-table->list ht)
   (let ([xs '()])
     (hash-table-for-each ht
                          (lambda (x v)
                            (set! xs (cons x xs))))
     xs))

(define (set->list s)
   (hash-table->list (set-ht s)))


But allocating a list just to iterate through the elements
just feels wrong.

So I thought I'd see what happened, if I used generators
instead. First the hash-table is converted into a
generator, and then each element is generated one at a
time:

(define-syntax :set
   (syntax-rules (index)
     ((:set cc var (index i) arg)
      (:parallel cc (:set var arg) (:integers i)) )
     ((:set cc var arg)
      (:do cc
           (let ((g (hash-table->generator (set-ht arg)))))
           ((x (g)))
           x
           (let ((var x)))
           #t
           ((g))))))

The problem is thus to write hash-table->generator efficiently.
As it turns out, the inversion via call/cc looses big time
to the convert-to-list approach.

So the next question, is: Is there a better way to turn
a hash-table into a generator?

-- 
Jens Axel Søgaard




Posted on the users mailing list.