[m-dev.] for review: new predicates in map.m

Peter Schachte pets at cs.mu.OZ.AU
Tue Oct 20 11:05:23 AEST 1998


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.

> (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 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,
map__key_bit_set/2....

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.


-- 
Peter Schachte                | The greater part of our happiness depends on
mailto:pets at cs.mu.OZ.AU       | our dispositions and not on our
http://www.cs.mu.oz.au/~pets/ | circumstances.
PGP: finger pets at 128.250.37.3 |     -- Martha Washington 



More information about the developers mailing list