since this is moving into speculation now, i am moving this topic to the devel forum...
On Tue, Sep 08, 2009 at 06:44:16PM +0200, Martin Stjernholm wrote:
what is the reason for this difference?
Historical, I think. Once upon a time multisets were implemented as sorted arrays.
hmm? i don't see how that explains why multisets are binary trees. the explanation you give below makes much more sense.
But there would be little use to have hash tables in two forms. If you want a hash table, use a mapping.
i would like an optimized multiset.
at this point the only difference between a mapping and a multiset is the fact that i can write it without values: (< "key", "key" >) vs: ([ "key":value ]), and that iteration over a multiset includes keys not just once.
i always saw multisets as syntactic sugar for a special form of mappings. were it not for the future plans...
Rather, the intention is at some point to extend multisets to be able to take values, just like mappings, and to take a custom sort function, so that their binary tree structure is fully usable from the pike level. Most low-level support for that is already in place.
sounds great. binary trees are a useful thing to have, although i wonder how they would relate to current use of multisets. aren't they a whole different thing alltogether?
and what about the necessary syntax change? we would get (< key, ...>) and (< key:value, ...>), at which point we might as well allow: ([ key,... ]) (ie: a hashtable based set implementation, aka syntax sugar for mapping(mixed:int(0..1))
and, hmm here is some wood for the fire of the discussion for tuple syntax. how about: tuple(mixed:mixed:mixed) foo = a:b:c;
then we can write arrays of tuples like this: ({ a:b:c, ... })
and the key:value pairs of mappings could be treated as tuples as well, same with multisets which would be generalized to: multiset(tuple(mixed:mixed)) leading naturally to multisets with values and mappings without values.
at least on the syntax level. in the implementation the problem would be that the first element of a tuple would have to be the key, and not the whole tuple. and nested tuples would not be possible with this syntax either.
greetings, martin.