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

[Fergus Henderson]

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__init(MA0),
		map__det_insert(MA0, K1, V1, MA1),
		map__det_insert(MA1, K2, V2, MA),
		map__init(MB0),
		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,
> map__key_bit_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
sorted order.

-- 
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 128.250.37.3        |     -- the last words of T. S. Garp.