[m-dev.] for review: new predicates in map.m
fjh at cs.mu.OZ.AU
Tue Oct 20 15:03:28 AEST 1998
On 20-Oct-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> On Tue, Oct 20, 1998 at 07:33:57AM +1000, Andrew Bromage wrote:
> > Zoltan Somogyi wrote:
> > > + % Given a map, return a list of all the keys in the map,
> > > + % in sorted order.
> > > +:- pred map__sorted_keys(map(K, _V), list(K)).
> > > +:- mode map__sorted_keys(in, out) is det.
> > There are already parts of the compiler which assume that map__keys/2
> > returns the keys in sorted order. (I know because I wrote one or two
> > of them; after asking, of course. <g>) Perhaps it would be better to
> > make that the default behaviour of map__keys/2.
> I don't think that's a good idea. Other implementations of maps (eg,
> hash talbes) might not find it natural to return the list sorted, so I
> don't think map__keys/2 should be specified to return a sorted list.
Let me ask another question, about map equality.
:- mode p(in, in, in, in) is semidet.
p(K1, V1, K2, V2) :-
map__det_insert(MA0, K1, V1, MA1),
map__det_insert(MA1, K2, V2, MA),
map__det_insert(MB0, K2, V2, MB1),
map__det_insert(MB1, K1, V1, MB),
MA = MB.
Should the unification `MA = MB' succeed?
> > (If order is not important, we could introduce another predicate which
> > returns the keys as a set.)
> My knee-jerk reaction to adding a map__sorted_keys/2 predicate is that
> it's unnecessary
What do you suggest as the alternative?
Using map__keys plus list__sort? That would be inefficient.
> and would tend to lead to library bloat. Let's see,
> we want map__keys/2, map__sorted_keys/2, map__key_set/2. What's next?
> I guess someone is bound to want to get the keys out in each kind of
> collection: map__key_bbb_set/2, map__key_234_set/2,
No, there'd just be one typeclass-polymorphic method map__key_set/2
which would work for any kind of set.
> On the other hand, since it's easy to collect the keys in sorted
> order, if performance is really critical and the cost of sorting an
> already sorted list is too great, then I guess there's a fair argument
> for it.
Yes, I think it is justified on performance grounds.
However I'm still undecided about whether it would be better
to just make map__keys guarantee that the keys are returned in
Fergus Henderson <fjh at cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger fjh at 126.96.36.199 | -- the last words of T. S. Garp.
More information about the developers