[Aldor-l] Set

[Christian Aistleitner]

Hello,

> Is there an argument against providing two functions
>
> set(l: List T): %    == per l;
> coerce(x: %): List T == rep x;
>
> directly in the Set implementation of libaldor?

as you only want to have it in Set itself and not in some abstraction (say
a not existing category SetType) I have no major objections.

Nevertheless, I would not like to see it.
When introducing such functions, you link List T to Set T and vice versa.
But such a linkage is unnatural to me.
Furthermore, I cannot see a real benefit.
Changes in Set's representation would require changes in these two
artificial functions as well.

I'd choose to keep separate things separate.

> I agree that the function 'set' is potentially dangerous, so maybe it
> should be called 'set!' to indicate that the programmer should be
> careful to provide only lists without duplicate elements as arguments to
> the function.

For me, the exclamation mark means “the function may act destructively on
some of its elements” and not “beware”. Your set and coerce functions do
not act destructively—they create memory aliases. So I'd consider set! a
bad choice.

It should suffice to put the condition that l must not contain duplicate
elements into set's documentation. Because the problematic things are not
Set's set, but the alterations of the passed List l. And these operations
already carry an exclamation mark.


> I'd like to avoid needless copying of data for cases where I know from
> some other sources that the input list cannot have duplicate elements.

The copying of data is only “needless”, as you know Set uses List
internally. Assume, tomorrow Stephen decides, it would be good to
implement Set via skip lists, heaps, or hash tables.
Then code for conversion between lists and sets have to be incorporated
into Set. But as List is just some arbitrary implementation of ListType,
its really artificial.

This relates to a problem I discussed some years ago with you in private.
In the aldor and algebra library there is a major problem with misusing
List. Lots of functions take parameters like ( a: List T ), when they
should really be ( LT: ListType T, a: LT ) or something in that sence. A
“any instance of” keyword would be usefull—other languages provide such
mechanisms by inheritance.


> Currently, in
>
> a: List L := [1,2,3];
> s: Set  L := [l for l in a];
> b: List L := [l for l in s];
>
> a and b are not equal, though a = reverse b. Unfortunately, it is
> nowhere written in the specification that the latter would always be
> true, so I cannot use it. And a=b would be better anyway, since for some
> reason, I would like to preserve the order of elements while passing
> through Set.

In mathematics, sets are not ordered per se. Use Lists if you rely on a
specific order (or SortedSet).

--
Kind regards,
Christian