Re: ADT Lib (3)

[Tim Teulings <tim@edge.ping.de>]

Hallo!

> > What about a nameing sheme when multiple "constructors" exist?

> Example?

Good question! Lets take a skip list,Hash or a BTree: You will have one
default constructor that uses internal defaults (defaults that a normaly
*good* and proven to work, e.g. the size of a hashtable using a
convinient prime number of medium size) and a constructor that enables
you to configure that parameter.

> If I'm defining a SortedList, then "being sorted" is an invariant.
> You can only add to a sorted list by calling Insert.  And Insert will
> kept the invariant.  Besides: a sorted list and a tree have a lot in
> common.  I want them to share as many properties as possible.
> Obviously, a temporarily unsorted tree is impossible.

Ok, than you are defining another abstract datatype besides our
proposed List. That is ok. However I would also implement a sort method
as proposed in our List.

> You are defining a relation.  We are talking abourt the same thing.  I
> would have it return a SHORTINT, though.

Yes. The trick is, that our relation is not part of our value but can
be defined else wehere. This way be can drop some intermediate Type
"Comparable" inheriting from Object.

> Why make an distinction here?  You have "write-only" files, and
> "read-only" files for applications quite often.  But in-memory data
> structure are usually read-write.  I don't understand the "hierarchy"
> remark.  Examples?

Yes. A sorting algorithm (we are speeking of a algorithm implemented in
form of a datastructure/operator and not as part of a datatype) can
only work on random access iterators. A array datatype for example does
support random access (in O(1)) and thus can be sorted. A hashtable
naturally does not support random access (in fact a serial access is
also on the edge between usefull and "not really part of the datatype")
and thus cannot be sorted. The differentiation is part of the Standard
template library, which is now part of the standard C++ library. I know
that the design of the STL is debatable. However the diverentiation
between various iterators does not show its usefullness when only
working with ADTs (there you may only need Readers and Writers) but
when implementing algorithms working on generic dadatypes trough
iterators and operators. You can check if a algorithm can be applied to
a datastructure by simply see if offered and used iterators match.

> > We also must add a method "Value", returning the current value
> > without moving.

> Why?

It is simply convinient and common practice. This way you need not to
store the result of a read. I think you are driving similarities
between iterators and file access too far.

> All of which are recursive.  The "real" (to quote Peter) iterator
> concept can only be provided at large cost, both in memory space and
> computation time.  "Iteration" vs "Recursion".

Sure? I'm not sure, but I think that itertaors can be applied to trees
without problem if you reduce the functionality of the iterator to be a
serial one. I must think about that, I admit. Tree are long ago :-)
A serial iterator lets you just go once from the start to the end, you
cannot skip nor you can go back.

> I don't like this statement, mostly it is just a bunch of truisms
> without any use.  Is the idea of a ADT library that pointless, because
> we cannot provide all possible implementations?

No of course not. There are always special datastructures that are more
efficient because they are hardcoded for a special problem. However,
because a library cannot cover all purposes it should not thus reduce
itself to one implementation. Of course we should reduce ourself to
some core ADTs first. However I see no problem in adding as much as
possible over time  as long as it all fits together. We need not to
defined all that ADTs yet, we should just preare ourself by using a good
naming convention. We will not reduce ourself to implement heap-sort,
we will do all other commonly used sorting algorithms, of course we
will implement that special variant that is the fasted in most cases
first ;-)

> And you have not answered my question: Why do we need a single-linked
> list in addition to a double-linked one?

A single list needs less ressources, which is always good if one can
work with the reduced interface. Also a single list - in the special
form of the LISP-like recursive list with no spcial head element - has
a different interface than a "normal" double list. It is in fact
a (slightly) different ADT.

Gting, Datenstrukturen und Algorithmen implements defined two ADTs

list1:
algebra list1
sorts   list, elem
opts    empty  : -> list
        first  : list -> elem
        rest   : list -> list
        append : list x elem ->list
        concat : list x list -> list
        isEmpty: list -> bool
...

list2:
algebra list2
sorts   list, elem, pos
opts    empty   : -> list
        front,
        last    : list -> pos
        next,
        previous: list x pos -> pos (or NULL)
        bol,
        eol     : list x pos -> bool
        insert  : list x pos x elem -> list
        delete  : list x pos -> list
        concat  : list x list -> list
        isEmpty : list -> bool
        find    : list x (elem -> bool) -> pos (or NULL)
        retrieve: list x pos -> elem
...

> That is the reason why all operations are type-bound procedures.  The
> base record can be extended to provide parameter (in, out, or mixed)
> to the applied functions.

Thas is exactly that what I wanted to know.


> P.S. I will try to restrict myself to one answer a day in the future ;-)

You should use the time I'm still here :-)

-- 
Gru...
       Tim.