Re: ADT Lib (4.2)

[Michael van Acken <mvacken@t-online.de>]

Ok, another quick reply.

> > Where to declare such extended riders?  Since a plain `Container's
> > semantics do not support either of these extensions, I feel they need
> > to be defined together with other abstract classes.  If all things
> > fail, we can always throw them into Container.Mod, of course, either
> > by declaring extensions of `Rider', or by putting everything into
> > `Rider' (similar to the way Channel.Reader/Writer does it).
> 
> As mentioned in my other mail, I'm not sure if a container baseclass
> should support iterators at all, in fact I'm not sure if a container
> baseclass is suitable in general. However I but suggest to put
> iterators into an own module named Iterator.Mod. The connection
> btetween ADTS and Iterators is not that strong that they must be place
> in the same module. Also, sinnce all classes are abstarct there is no
> need to put them into the same module to access internal attributes and
> methods.

Actually, I don't really care in which module `Rider' is declared.  I
am more concerned about the type in the receiver of the `NewIterator'
method. 

Also: Every ADT needs to provide its own implementation of iterators.
This makes it pretty pointless to split ADT and iterator into separate
modules.

> Also I'm not sure, if a Writer should be a superset of a Reader? Is
> this really true?

A Reader is not a Writer.  A Writer is not a Reader.  One can't be
implemented as an extension of the other.

> However it is the only way to generical copy, move or sort elements. You
> need Inserters and Updates with a clear semantic for a number of
> algorithms. Note, I do not propose to put them into a container
> baseclass but their should be special Iterator classes for that. ADTs
> then can choose to support them or not.

Your obession with generic algorithms is noted  ;-)  I do not share
it.

> The procedure Apply would have the following parameter:
> 
> A iterator (a simple sequential one would be enough) and the operator.
> The Apply method simply would use the iterator to get acess to all
> values and then would apply Operator an each value (note, that this is a
> dangerous think, since it bears a hidden update action. What would
> happen if we change a value that is a sort criterium?). Implementing
> Apply as a simple procedure only working on iterators has the flowwing
> advantage: We only need to describe the Apply algorithm once. We do not
> need it to be implemented in every ADT. ADTs do not need to support an
> apply algorithm (or any other algo) directly. In fact we will save a
> lot of simple code. We can work generical on any ADT that at least
> supports a sequential iterator.

Your description is a little bit one sided.  You miss one advantage of
this approach: The user can select the iterator, and with it the
enumeration order.  

But you also miss a severe disadvantage: The hidden cost.  A tree
iterator is an expensive thing.  You might even manage to have a run
time cost that exceeds O(n).  Having a single, but stupid and costly,
implementation of this function, is no benefit.

Example: If implemented this way, your way to `Copy' an unsorted list
by successive insertion will (hopefully) be O(n).  The same algorithm
on a simple binary tree will be O(n^2).  

> An example for the Map shows another nice feature:
> 
> The Map algo would have the following parameter: A sequential iterator,
> the function and an insert iterator. I do not describe here how the
> Map procedure the function do interact to select the value that should
> be inserted by the insert iterator, there are a number of possible
> implementation which we can discuss later. However, besides the already
> given advantages, we now see the power of a generic inserter. We can
> read, filter, move, copy values is such a way that neither the type of
> the source nor of the destination ADT must be nown to us.

I do not see anything.  Ok, I may be blind ;-)  

What I do see is a lot of prose.  You have presented a lot of text on
this topic.  But nothing has been forthcoming that can be turned into
a part of the (slowly) evolving set of modules.  Until you present
something "hard" (instead of "soft" prose), I fear we will never get
past the stage of a spirited discussion.  Have a nice holiday.

I have made my current (small) set of files available at
http://home.t-online.de/home/mvacken/

-- mva