Re: [boost] Re: (infinite) sequences using recurrence relations

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-06 19:18:41

Eric Ford wrote:

> So, yes, I beleive the container for a sequence generated via a
> recurrence relation will need a new concept.  

        No. Most people don't understand STL. Containers
are NOT PART OF STL. They are provided merely as a way of
creating some useful iterators. There are rules in the Standard,
because the containers have to have requirements.

        But containers are NOT PART OF STL. STL is concerned
with algorithms and iterators. It is NOT concerned with how
you produce the iterators. Thats the whole point of it.
[But read on before you argue :-]

        So no new concept is required to support mathematical
sequences, except in the minds of those who mistakenly believe
containers are part of STL. 

        STL is about generic algorithms, and the way in which
the concept of sequence as embodied by the notions of iterator
DECOUPLES the algorithms from the containers they operate on.

        To really understand this, you need to see that
STL algorithms are polymorphic in high order: they're NOT
just parametic on the value type, they're parametric on the
iterator type as well. Thus, 'for_each' works on every
'kind' of input iterator, as well as every value type 
for a particular kind.

        Containers, on the other hand, are basically concrete:
they're only 'polymorphic' in the trivial sense of 
being parametric on the value type. More precisely, a given
container such as a tree, can support a lot of different
iterators (such as depth first or breadth first ordering).

        Is a tree container abstract? No, it is a concrete
data structure. Different kinds of tree support different
kinds of iterators too. Is a tree a sequence?? 

        No, of course not. But all its iterators 
scan sequences. 

        Note that this 'higher order' polymorphism
is not something trivial: 

        Most FP languages like SML do NOT 
support such higher order polymorphism. I've actually
worked on one (FISh 2) that does, and it is a major
theoretical advance. The closest is Haskell, which
requires you define 'map' for each data structure.
(or is it fold? I'm not a Haskell programmer).
STL is actually close to Haskell, in that
iterators are somehow the dual of a functional map.

        So .. it's important not to trivialise STL
by thinking about containers. A container is just a factory
for creating iterators. The details of the data structure
are closely related to what category of iterators you can produce.
(eg: in a tree, is there an uplink from child to parent?)

        So I'm now going to completely invert my original
claim! The whole point of STL is that it is a vehicle
for studing the intricate details of data structures,
precisely because the iterator concept allows one
to factor algorithms out of the picture: one can think
not about 'recursive descent on a tree' as a tree algorithm,
but about the complexity of an iterator for a given tree
data structure which supports a depth first visitation
order that makes 'for_each' into a recursive descent.

        It took me a while to see that the complexity
requirements on iterators are absolutely fundamental:
you can't do a 'recursive visitiation' on a tree with
an iterator without a child->parent link (unless you want
to keep a stack inside each iterator :-)

        [Basically, for some data structure D, the
mapping from D to S, where S is a linear sequence,
is a functor preserving 'some of the structure' of D,
and that functor preserves structure because of the
constraint on complexity: but I really don't know
how to make this precise, and neither did Stepanov]

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net