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.