Subject: Re: [SWIPL] keysort

From: Paul Singleton <[email-masked]>
Date: Wed, 28 Feb 2001 23:55:16 +0000

"Richard A. O'Keefe" wrote:

> ...you cannot actually implement bag in terms of ordset(pair)
>         without cracking open the ordset abstraction.  For example, taking
>         the union of two ordsets of pairs is *NOT* the same as taking the
>         union of two bags, so special-purpose code has to be written
>         anyway.  That is, you have to work *inside* the ordset abstraction.

OO folk would say you have to override some of the operations (others would
still be valid); I guess this could be done without reference to the actual
representations of either ordset or pair?  And maybe PE could rewrite it to
be efficient?  in principle at least...
 
> If you meant why isn't it list(pair(Element,integer)),

Probably :-) except I assumed there'd be some benefit in keeping the list
ordered on the elements?

> then the answer is
> time, space, debugging, and error prevention.
> 
> Debugging:
>         By attaching a distinctive functor to bags, I could give them their
>         own portray/1 definition.

...this being the only way to attach an operation to a type :-)

(thinks: 'CB8AD857-BBEE-11D4-B806-525400DFC059'/3 would have been more
distinctive :-)

> Error prevention:
>         I did NOT want bags to unify with lists.  Distinct abstract data
>         types should have implementations that do not unify.

Even where one is a specialisation on the other?

>         And wrappers
>         are Bad Style, so it is not enough to put a wrapper around a list.

Wrappers don't appeal to me, but I can't see why they are "not enough":
they seem to do the job just fine.  You only pay the overhead once per
bag, not per element, both in space and in operations such as intersection.
The use of a list becomes a purely internal matter.  Sadly the wrapper
adds to (but not compounds) the already higher-than-necessary costs of
the list-of-pairs representation.

> Since special-purpose code had to be written anyway (for correctness),
> and a special-purpose data structure had to be written anyway (so that
> it would not incorrectly match something with different properties), it
> seemed good to me to use a design that was time- and space-efficient.

I never doubted that you'd made a justifiable decision, but I was
interested in your rationale.  I assumed that, for a long-lived, perhaps
widely-used library, run-time efficiency wins over what I called "design
time efficiency".

> You should combine existing data types WHEN THAT WILL WORK.

Yes, but when we do, we lose the benefits of distinctiveness :-/

Given that Prolog denies us the "best of both worlds" compromises which 
OO supports (with inheritance and overriding), I'm inclined to say: do
it whichever way you want: it will be locally optimum in some sense,
and you can claim that your values at the time made it the best choice!

Paul Singleton