[Aldor-l] Set

[Christian Aistleitner]

Hello,

On Thu, 05 Oct 2006 12:04:40 +0200, Ralf Hemmecke <ralf at hemmecke.de> wrote:

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

no! Information hiding is the key. You may exploit things like "In  
LinkedList I can insert elements at the list's head in O(1)", as this is  
part of the specification. But relying on a specific internal  
representation is error prone.

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

If you do not need your data to be an element of the domain Set, you can  
easily implement the desired domain. I would not tinker with Set and  
connecting it to List, but implement LinkedListWithoutDuplicates using  
List.

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

I meant overall benefit. Things like “better structure” or “better design”.

Tuning the base library (libaldor) of a general purpose programming  
language (Aldor) to a specific third-party library (Aldor-combinat), is  
not the best choice from my point of view.

However, your Aldor-combinat example was just an example. Are there other  
examples showing the benefit for the library itself?


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

Yes, and I like that. There are a lot of data structures, that shuffle  
lots of elements around when inserting a single element. For such data  
structures, it would be hard to keep the order of ther elements when  
iterating over the structure.
Currently it would be possible to switch Set to such data structures.
Restricting the order, would make things harder.

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

Yes. But is SetSpecies a set keeping the order of its elements? Then give  
it a “descriptive name”, so other people can use it as well.

>> 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 Aldor, an object knows its type. Only data does not know its type.
Consider

   local someInt: Integer := 12345

. Then it is known that someInt is of type Integer. But it is not know  
that the in  memory representation of 12345 is of type Integer.

 From my feeling, an “any instance of” should be perfectly possible with  
the current Aldor language. Currently, you can model

   ( l: any instance of ListType T )

by

   ( LT: ListType T, l: LT )

. “any instance of” would just allow you to eliminate the first parameter.  
It would make code more compact and more readable without losing its  
expressivness.
(Of course we would also need an operator allowing to obtain the current  
value of “any instance of ListType T”.)

--
Kind regards,
Christian