Re: Scheme style auto-resizing hashtable (fwd)

[Per Bothner <bothner@cygnus.com>]

> Reading SICP, stream primitives are used to do this sort of of "iterator" 
> thing, right?

The SICP stream primitives are one very powerful and elegant
way to do iteration.  But a SICP stream is not an "iteraor" in the
sense of "an object that gives you the next value each time you call it".
A SICP stream is a delayed list, which does provide similar
functionality as iterators.  However, the SICP implementation
does cause a cons cell to be created for each element to be
iterated over.  The main difference from regular lists is that
cons cells are only created "as needed" - when you access an
element.  Thus the model can handle infinite "lists".

Thus SICP streams still involve creating a "lazy cons" for each
element of the collection that you are iterating over (unless
you break off the iteration early).  This makes streams much
more expensive than cursor-style iterators.  On the other hand,
Waters' "series" implementation (see CLtL:2 appendix A) suggests
that with some compiler smarts it may be possible to remove
much of the overhead in most cases (assuming the compiler is
allowed to inline the series functions).

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner