[chuck-users] get hash keys from associative array

[Robin Haberkorn]

On 27/09/12 00:45, Kassen wrote:
> 
> I think you are right and that this leads to some interesting
> consequences. Since we don't have things like lists or vectors we tend
> to use arrays for a lot; they are our one generic higher level
> structure. Because of that, over the last few versions, we got extra
> features for them; ways to change the size and a sort of push/pop
> structures making them usable like a sort of stack.
>
> ...
> 
> I am, BTW, not at all opposed to just having one generic higher level
> structure; it does add coherence and clarity and avoids conversions,
> assuming our one such structure behaves very well.
> 
> Yours,
> Kas.

Hi!

Firstly, just as an info: ChucK maps are implemented internally as
red-black trees, not hash maps.

Secondly, arrays/maps are not the only higher-level (aggregate)
data type in ChucK. There are also classes, which are well suited for
record/structure-like use cases.
If you want a language with only one higher-level data type, have a look
at Lua. It has "tables" which are simply RB-trees. They are used as
arrays (all keys are integer and consecutively start with 1),
associative arrays (some other type of key - every key may have a
different type) and classes/objects (table values may be functions and
there's a hierarchy of tables via "metatables"). All of this is possible
by adding syntactic sugar to the language, e.g. for constructing tables.

While I think that ChucK arrays should be more generic (e.g. it should
be possible to construct maps using "[ ... ]" expressions), I think it's
a good thing that ChucK has a separate class type, as it is much more
explicit than Lua classes and (theoretically) allows better optimizations.

Regarding the question of iterating maps: Of course that would be nice.
But doing this by simply having a method that returns all keys as an
array is inefficient, since that requires a complete traversal of the
RB-tree (O(n)) to get all keys, followed by RB-tree accesses (O(log(n)))
for every key. That is a complexity of O(n*(log(n) + 1)) for a complete
iteration while it is theoretically possible in O(n).
Doing it in O(n) however requires you to have a concept of iterators and
iterator-loops, adding much complexity to the language. In the simplest
case you need a special for-loop, like
for (key, value in map) {...}

If you need an efficient map iteration right now, consider implementing
your own RB/AVL-tree data structure using ChucK classes ;-)

Best regards,
Robin