[Aldor-l] Set

[Ralf Hemmecke]

Hello,

maybe this will start a discussion about the design of LibAldor. As 
Christian pointed out in his last post, I also think that it is not 
optimal. LibAldor should lay grounds for mathematical datastructures. So 
I think is should provide LinkedList, DoublyLinkedList, all the 
different sorts of queues, arrays, etc, etc. And basically the name 
should give some hint about which internal datastructure is used.

For some algorithm it makes sense to know what the internal 
datastructure is.

On 10/05/2006 09:20 AM, Christian Aistleitner wrote:
> 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.

I completely understand that. All I want is something like

   LinkedListWithoutDuplicates

with the semantics that the order of elements is never exchanged. (Note 
that I might not be able to compare the elements themselves.)

> Furthermore, I cannot see a real benefit.

Well, one of the applications would be in Aldor-combinat. List and Set 
are really very different combinatorial species.

Species are endofunctors over the category of finite sets.
So basically if U={1,2} is a set then F[U] is the set of all 
F-structures. Example, if F=L is the species of lists then 
L[U]={[1,2],[2,1]}.
But now if V={2,1}, we clearly have U=V and L[V]={[2,1],[1,2]} = L[U].
Now suppose I want to generate the elements of L[W] for any set W always 
in the same order. That is, the algorithm should first return [1,2] and 
then [2,1] no matter whether I input U or V. (The order matters since 
that is used for what is called "ranking" and "unranking", ie, forming a 
bijection between natural numbers and the structures.)
Think about what work it would be if we consider all the n! different 
internal representations of the set {1,...,n}.

Currently Set does not even guarantee that

l: Set Integer := [1,2];
for i in l repeat stdout << l;
for i in l repeat stdout << l;

prints 1212 or 2121 but not 1221 and not 2112.
It is not written in it's API.

> Changes in Set's representation would require changes in these two
> artificial functions as well.
> 
> I'd choose to keep separate things separate.

Well, it seem that I have to implement my own SetSpecies. :-(

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

Yes, yes. Implementation details should be kept secret. But if the 
library does not provide what I want I either

a) complain at aldor.org what I just did
b) rewrite (essentially equal) code myself and thus duplicate code :-(
c) if b) is to hard a task, turn away and look for some better library 
(which does not exist currently in Aldor).

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

But such "any instance of" would require that an object knows about its 
type. We don't have that in Aldor.

In many cases, one could use Generator instead, though. But I agree, 
that Generator is not the solution for all use cases.

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

List is bad. LinkedListWithoutDuplicates would be better, but it's a bit 
long. :-(

Ralf