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

[Peter Schachte]

On Tue, Oct 20, 1998 at 03:03:28PM +1000, Fergus Henderson wrote:
> 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:

> 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?

Yes.  Maps should be independent of the order in which elements are
inserted.  If you take the oposite view, then you have to make sure
that two maps unify iff the elements were added in the same order.

I guess you'll be needing a custom equality predicate....

> > 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.

Yes.  How inefficient is sorting a sorted list?  I would expect it to
be linear (you're not using an unmodified quicksort are you?), and
since the cost of collecting the keys is linear, it's only a constant
factor difference.

> > Let's see,
> > we want map__keys/2, map__sorted_keys/2, map__key_set/2.  What's next?
>
> No, there'd just be one typeclass-polymorphic method map__key_set/2
> which would work for any kind of set.

If you push it to "any kind of collection," and replace map__keys with
that predicate, then that sounds really good to me.

> 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.

On the theory that the current map type is a prototypical instance of
the map type class (in the sense that map's interface would be the set
of required predicates/functions for the type class), I think it would
be a mistake to specify the order, because for some instances of that
type class it would be inefficient to do so.

The nice, declarative way to do this would be declare that this
implementation of map__keys returns the list sorted (but not make that
declaration part of the interface), and also declare as part of the
interface for sort/2 that sorted(X), sort(X, Y) => X = Y, then call
map__keys(M, L0), sort(L0, L), and have the compiler turn the sort
call into a unification.

Someday.

-- 
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