[racket] building iterators on trees

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Nov 9 15:00:02 EST 2011

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





Posted on the users mailing list.