[racket] building iterators on trees
On Nov 9, 2011, at 2:52 PM, Danny Yoo wrote:
> I've been thinking about how to support hash-iterate-first and
> hash-iterate-next in Whalesong. In Whalesong, my functional hash
> implementation is based on left-leaning red-black trees. The
> hash-iterate-* functions are a little weird for me since they return
> numbers, and I had expected them to produce some opaque, structured
> value.
>
> Since I can only use numbers, it makes iteration weirder since I'm
> dealing with a non-linear structure. I cooked up a quick prototype of
> an approach:
>
> http://www.wescheme.org/openEditor?publicId=shady-clunk-blase-saber-decay
>
> treating the number as binary digits, and using it as a description of
> a path through the tree.
>
> Is this a reasonable approach?
This idea has a name in the FP community: director strings. It's the ultimate generalization of combinatorial programming (S distributes arguments, K distributes arguments in a different way, and director strings are general codes for distribution in a tree). -- Matthias